Skip to content

Parser

Jump to bottom
andreas-eberle edited this page Nov 9, 2014 · 33 revisions

Grammatik

Die Grammatik ist wegen mancher linksrekursiver Produktionen für kein k LL(k).

In jedem Fall muss in diesen Produktionen die linksrekursion für den rekursiven Abstieg eliminiert werden (vermutlich auch noch andere Produktionen):

  • LogicalOrExpression -> (LogicalOrExpression ||)? LogicalAndExpression
  • LogicalAndExpression -> (LogicalAndExpression &&)? EqualityExpression
  • EqualityExpression -> (EqualityExpression (== | !=))? RelationalExpression
  • RelationalExpression -> (RelationalExpression (< | <= | > | >=))? AdditiveExpression
  • AdditiveExpression -> (AdditiveExpression (+ | -))? MultiplicativeExpression
  • MultiplicativeExpression -> (MultiplicativeExpression (* | / | %))? UnaryExpression

This part will be done with Precedience Climbing, the theoretical grammar is:

  • Expression -> AssignmentExpression
  • AssignmentExpression -> LogicalOrExpression (= AssignmentExpression)?
  • LogicalOrExpression -> LogicalAndExpression LogicalOrExpression'
  • LogicalOrExpression' -> (|| LogicalAndExpression LogicalOrExpression')?
  • LogicalAndExpression -> EqualityExpression LogicalAndExpression'
  • LogicalAndExpression' -> (&& EqualityExpression LogicalAndExpression')?
  • EqualityExpression -> RelationalExpression EqualityExpression'
  • EqualityExpression' -> ((== | !=) RelationalExpression EqualityExpression')?
  • RelationalExpression -> AdditiveExpression RelationalExpression'
  • RelationalExpression' -> ((< | <= | > | >=) AdditiveExpression RelationalExpression')?
  • AdditiveExpression -> MultiplicativeExpression AdditiveExpression'
  • AdditiveExpression' -> ((+ | -) MultiplicativeExpression AdditiveExpression')?
  • MultiplicativeExpression -> UnaryExpression MultiplicativeExpression'
  • MultiplicativeExpression' -> ((* | / | %) UnaryExpression MultiplicativeExpression')?

Geänderte Produktionen (work in progress)

Um auf SLL(3) zu kommen. Weniger sollte nicht gehen, da IDENT[] a und IDENT[1] sonst nicht unterschieden werden können:

  • PrimaryExpression -> null | false | true | INTEGER_LITERAL | PrimaryIdent | this | ( Expression ) | new NewExpression
  • PrimaryIdent -> IDENT | IDENT ( Arguments )
  • NewExpression -> IDENT () | BasicType NewArrayExpression
  • NewArrayExpression -> [Expression] ([])*
  • PostfixOp -> MethodInvocationFieldAccess | ArrayAccess
  • MethodInvocationFieldAccess -> . IDENT MethodInvocationFieldAccess'
  • MethodInvocationFieldAccess' -> ( Arguments ) | epsilon

parse-Funktionen (wip)

Ich denke eine Gegenüberstellung von Produktionen, wie sie im Sprachbericht aufgeführt werden und den Produktionen, wie wir sie im Parser modofiziert implementieren, ist sinnvoll.

parseProgram:

  • Program -> ClassDeclaration*
  • ClassDeclaration -> class IDENT { ClassMember* }

geändert in

  • Program -> epislon | class IDENT { ClassMember' } Program

parseClassMember:

  • ClassMember -> Field | Method | MainMethod
  • Field -> public Type IDENT ;
  • MainMethod -> public static void IDENT ( String [ ] IDENT ) Block
  • Method -> public Type IDENT ( Parameters? ) Block

geändert in

  • ClassMember' -> public ClassMember''
  • ClassMember'' -> MainMethod' | Member
  • MainMethod' -> static void IDENT ( String [ ] IDENT ) Block
  • Member -> Type IDENT Member'
  • Member' -> ; | ( Parameters? ) Block

parseParameters:

  • Parameters -> Parameter (, Parameters)?

parseParameter:

  • Parameter -> Type IDENT

parseType:

  • Type -> Type [] | BasicType
  • BasicType -> int | boolean | void | IDENT

geändert in

  • Type -> Basictype ([])?
  • BasicType -> int | boolean | void | IDENT

parseStatement:

  • Statement -> Block | EmptyStatement | IfStatement | ExpressionStatement | WhileStatement | ReturnStatement

parseBlock:

  • Block -> { BlockStatement* }

parseBlockStatement:

  • BlockStatement -> Statement | LocalVariableDeclarationStatement
  • Statement -> Block | EmptyStatement | IfStatement | ExpressionStatement | WhileStatement | ReturnStatement

geändert in

  • BlockStatement -> Block | EmptyStatement | IfStatement | ExpressionStatement | WhileStatement | ReturnStatement | LocalVariableDeclarationStatement

parseLocalVariableDeclarationStatement:

  • LocalVariableDeclarationStatement -> Type IDENT (= Expression)? ;

parseEmptyStatement:

  • EmptyStatement -> ;

parseWhileStatement:

  • WhileStatement-> while ( Expression ) Statement

parseIfStatement:

  • IfStatement -> if ( Expression ) Statement (else Statement)?

parseExpressionStatement:

  • ExpressionStatement -> Expression ;

parseReturnStatement:

  • ReturnStatement -> return Expression? ;

Resultierende Grammatik

  • Program -> epislon | ( class IDENT { ClassMember' } Program ) *

  • ClassMember' -> public ClassMember''

  • ClassMember'' -> MainMethod' | Member

  • MainMethod' -> static void IDENT ( String [ ] IDENT ) Block

  • Member -> Type IDENT Member'

  • Member' -> ; | ( Parameters? ) Block

  • Parameters -> Parameter (, Parameters)?

  • Parameter -> Type IDENT

  • Type -> Basictype ([])*

  • BasicType -> int | boolean | void | IDENT

  • Statement -> Block | EmptyStatement | IfStatement | ExpressionStatement | WhileStatement | ReturnStatement

  • Block -> { BlockStatement* }

  • BlockStatement -> Block | EmptyStatement | IfStatement | ExpressionStatement | WhileStatement | ReturnStatement | LocalVariableDeclarationStatement <-- SLL(3)

  • LocalVariableDeclarationStatement -> Type IDENT (= Expression)? ;

  • EmptyStatement -> ;

  • WhileStatement-> while ( Expression ) Statement

  • IfStatement -> if ( Expression ) Statement (else Statement)?

  • ExpressionStatement -> Expression ;

  • ReturnStatement -> return Expression? ;

  • Precedence climbing for expressions

  • UnaryExpression -> PostfixExpression | (! | -) UnaryExpression

  • PostfixExpression -> PrimaryExpression (PostfixOp)*

  • PostfixOp -> MethodInvocationFieldAccess | ArrayAccess

  • MethodInvocationFieldAccess -> . IDENT MethodInvocationFieldAccess'

  • MethodInvocationFieldAccess' -> ( Arguments ) | epsilon

  • ArrayAccess -> [ Expression ]

  • Arguments -> (Expression (, Expression)*)?

  • PrimaryExpression -> null | false | true | INTEGER_LITERAL | IDENT PrimaryIdent | this | ( Expression ) | new NewExpression

  • PrimaryIdent -> ( Arguments ) | epsilon

  • NewExpression -> IDENT NewIdentExpression | boolean NewArrayExpression | int NewArrayExpression | void NewArrayExpression

  • NewArrayExpression -> [Expression] ([])*

  • NewIdentExpression -> () | NewArrayExpression

Clone this wiki locally