Skip to content

Attributed grammar

Jump to bottom
valentinz edited this page Nov 16, 2014 · 53 revisions

LAG(1) not possible, since methods can be used before they are declared.

Attributierte Grammatik für das Bauen des AST

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

Sammeln der Declarations: ClassMember_0.decls_in = {}

ClassMember'_i.decls_in += ClassMember''_i-1.decls_out

Das letzte Member n enthält alle Deklarationen

Weiterreichen der Klassen Program1.classes_in = new ClassDeclaration(ClassMember'_n.decls_out)

Die letzte Klasse n enthält alle Klassen Program.node = new Program(Program_1.classes_out)

  • ClassMember' -> public ClassMember''

ClassMember''.decls_in = ClassMember'.decls_in

ClassMember'.decls_out = ClassMember''.decls_out

  • ClassMember'' -> MainMethod'

MainMethod'.decls_in = ClassMember''.decls_in

ClassMember''.decls_out = MainMethod'.decls_out

  • ClassMember'' -> Member

Member.decls_in = Classmember''.decls_in

ClassMember''.decls_out = Member.decls_out

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

MainMethod'.decls_out = MainMethod'.decls_in + new MethodDeclaration(void, new Parameters(), Block.stmts)

  • Member -> Type IDENT Member'

Member'.decls_in = Member.decls_in

Member.decls_out = Member'.decls_out

Member'.type = Type.node

Member'.name = IDENT.lexval

  • Member' -> ;

Member'.decls_out = Member'.decls_in + new FieldDeclaration(Member'.type, Member'.name)

  • Member' -> ( Parameters? ) Block

Member'.decls_out = Member'.decls_in + new MethodDeclaration(Member'.type, member'.name, Parameters.params_out, Block.smts)

  • Parameters -> Parameter (, Parameters1)?

Parameters1.params_in = Parameters.params_in + Parameter.node

Parameters_out = Parameter.in + Parameter.node

  • Parameter -> Type IDENT

Parameter.node = new ParameterDefinition(Type.node, IDENT.lexval)

  • Type -> Basictype ([])*

Type.node = new BasicType(BasicType.type, arrayDepth)

  • BasicType -> int | boolean | void | IDENT

For int: BasicType.type = int.lexval. Equivalent for boolean, void and IDENT.

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

For Block: Statement.stmts = Block.stmts. Equivalent for all other.

  • Block -> { BlockStatement* }

BlockStatement_i.smts = BlockStatement_i.smts + BlockStatement_i+1.stmts

Block.node = new Block(BlockStatement_n_stmts)

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

For Block: BlockStatement.stmts_out = BlockStatement.stmts_in + Block.node

For EmptyStatement: BlockStatement.stmts_out = BlockStatement.stmts_in + EmptyStatement.node

Equivalent for all others.

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

LocalVariableDeclarationStatement.node = new LocalVariableDeclarationStatement(Type.node, IDENT.lexval, Expression.node)

  • EmptyStatement -> ;

EmptyStatement.node = {}

  • WhileStatement-> while ( Expression ) Statement

WhileStatement.node = new WhileStatement(Expression.node, Statement.node)

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

IfStatement.node = new IfStatement(Expression.node, Statement.node, Statement1.node)

  • ExpressionStatement -> Expression ;

ExpressionStatement.node = Expression.node

  • ReturnStatement -> return Expression? ;

ReturnStatement.node = new ReturnStatement(Expression.node)

UnaryExpression -> PostfixExpression | (! | -) UnaryExpression1

  • if(!)
  • UnaryExpression.node = new LogicalNotExpression(UnaryExpression1.node)
  • if(-)
  • UnaryExpression.node = new NegateExpression(UnaryExpression1.node)
  • else
  • UnaryExpression.node = PostfixExpression.node

PostfixExpression -> PrimaryExpression (PostfixOp)*

  • PostfixExpression.node = PostfixOp.node
  • PostfixOp.expr = PrimaryExpression.node
  • if no PostfixOp
  • PostfixExpression.node = PrimaryExpression.node

PostfixOp -> MethodInvocationFieldAccess | ArrayAccess

  • if(.)
  • PostfixOp.node = MethodInvocationFieldAccess.node
  • MethodInvocationFieldAccess.expr = PostfixOp.expr
  • if([)
  • PostfixOp.node = ArrayAccess.node
  • ArrayAccess.expr = PostfixOp.expr

MethodInvocationFieldAccess -> . IDENT MethodInvocationFieldAccess'

  • MethodInvocationFieldAccess.node = MethodInvocationFieldAccess'.node
  • MethodInvocationFieldAccess'.expr = MethodInvocationFieldAccess.expr
  • MethodInvocationFieldAccess'.ident = IDENT.lexval

MethodInvocationFieldAccess' -> ( Arguments ) | epsilon

  • if(()
  • MethodInvocationFieldAccess'.node = new MethodInvocationExpression(MethodInvocationFieldAccess'.expr, MethodInvocationFieldAccess'.ident, Arguments.node)
  • else
  • MethodInvocationFieldAccess'.node = new VariableAccessExpression(MethodInvocationFieldAccess'.expr, MethodInvocationFieldAccess'.ident)

ArrayAccess -> [ Expression ]

  • ArrayAccess.node = new ArrayAccessExpression(ArrayAccess.expr, Expression.node)

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

  • `Arguments.node = Arguments.node + Expression_i.node`` for all i

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

  • if(null)
  • PrimaryExpression.node = new NullExpression()
  • if(this)
  • PrimaryExpression.node = new ThisExpression()
  • if(boolean)
  • PrimaryExpression.node = new BooleanConstantExpression(booleanvalue)
  • if(int)
  • PrimaryExpression.node = new IntegerConstantExpression(intvalue)
  • if(()
  • PrimaryExpression.node = Expression.node
  • if(IDENT)
  • PrimaryExpression.node = PrimaryIdent.node
  • PrimaryIdent.ident = IDENT.lexvalue
  • if(new)
  • PrimaryExpression.node = NewExpression.node

PrimaryIdent -> ( Arguments ) | epsilon

  • if(()
  • PrimaryIdent.node = new VariableAccessExpression(null, PrimaryIdent.ident)
  • else
  • PrimaryIdent.node = new MethodInvocationExpression(null, PrimaryIdent.ident, Arguments.node)

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

  • if(IDENT)
  • NewIdentExpression.ident = IDENT.lexval
  • NewExpression.node= NewIdentExpression.node
  • else
  • NewExpression.node = NewArrayExpression.node
  • NewArrayExpression.type = boolean | int | void

NewArrayExpression -> [Expression] ([])*

  • NewArrayExpression.type = new ArrayType(NewArrayExpression.type)
  • for all [] pairs
  • NewArrayExpression.type = new ArrayType(NewArrayExpression.type)
  • NewArrayExpression.node = new NewArrayExpression(NewArrayExpression.type, Expression.node)

NewIdentExpression -> () | NewArrayExpression

  • if(()
  • NewIdentExpression.node = new NewObjectExpression(NewIdentExpression.ident)
  • else
  • NewIdentExpression.node = NewArrayExpression.node

UnaryExpression and following (for semantic analysis not AST construction)

NewArrayExpression :: Type Expression

  • if(Expression.type = int)
  • NewArrayExpression.type = new Array(Expression.value, Type.type)
  • NewArrayExpression.basictype = Type.type

NewObjectExpression :: Symbol

  • if(NewObjectExpression.umg.search(Symbol.ident))
  • NewObjectExpression.decl = NewObjectExpression.umg.search(Symbol.ident)
  • NewObjectExpression.type = class

NullExpression ::

  • NullExpression.type = null

ThisExpression ::

  • ThisExpression.decl = ThisExpression.umg.search(this.class)
  • ThisExpression.type = class

BooleanConstantExpression :: value

  • BooleanConstantExpression.value = value.booleanvalue

IntegerConstantExpression :: value

  • IntegerConstantExpression.value = value.intvalue

Symbol :: symbol

  • Symbol.value = symbol.lexvalue

VariableAccessExpression :: Expression Symbol

  • if(Expression.type = class)
  • VariableAccessExpression.decl = VariableAccessExpression.umg.search(Expression.value(Namespace), symbol.value)
  • VariableAccessExpression.type = VariableAccessExpression.decl.type
  • if(Expression.value = null)
  • VariableAccessExpression.decl = VariableAccessExpression.umg.search(this.class, symbol.value)
  • VariableAccessExpression.type = VariableAccessExpression.decl.type

MethodInvovationExpression :: Expression Symbol (Expression)*

  • if(Expression.type = class)
  • MethodInvovationExpression.decl = MethodInvovationExpression.umg.search(Expression.value(Namespace), symbol.value)
  • MethodInvovationExpression.returntype = MethodInvovationExpression.decl.returntype
  • MethodInvovationExpression.param = List<Expression> Expressions.value
  • if(Expression.value = null)
  • MethodInvovationExpression.decl = MethodInvovationExpression.umg.search(this.class, symbol.value)
  • MethodInvovationExpression.returntype = MethodInvovationExpression.decl.returntype
  • MethodInvovationExpression.param = List<Expression> Expressions.value

ArrayAccessExpression :: Expression1 Expression2

  • if(Expression1.type = array && Expression2.type = int)
  • ArrayAccessExpression.decl = ArrayAccessExpression.umg.search(Expression1.value)
  • ArrayAccessExpression.type = Expression1.basictype

LogicalNotExpression :: Expression

  • if(Expression.type = boolean)
  • LogicalNotExpression.type = boolean
  • LogicalNotExpression.value = !(Expression.value)

NegateExpression :: Expression

  • if(Expression.type = boolean)
  • NegateExpression.type = boolean
  • NegateExpression.value = -(Expression.value)

BinaryExpression

Expression -> AssignmentExpression

  • Expression.node = AssignmentExpression.node

AssignmentExpression -> LogicalOrExpression AssignmentExpression'

  • AssignmentExpression'.in = LogicalOrExpression.node
  • AssignmentExpression.node = AssignmentExpression'.node

AssignmentExpression' -> epsilon

  • AssignmentExpression'.node = AssignmentExpression'.in

AssignmentExpression' -> = AssignmentExpression

  • AssignmentExpression'.node = new Assignment(AssignmentExpression'.in, AssignmentExpression.node)

LogicalOrExpression -> LogicalAndExpression LogicalOrExpression'

  • LogicalOrExpression'.in = LogicalAndExpression.node
  • LogicalOrExpression.node = LogicalOrExpression'.node

LogicalOrExpression' -> epsilon

  • LogicalOrExpression'.node = LogicalOrExpression'.in

LogicalOrExpression'1 -> || LogicalAndExpression LogicalOrExpression'2

  • LogicalOrExpression'2.in = new LogicalOr(LogicalOrExpression'1.in, LogicalAndExpression.node)
  • LogicalOrExpression'1.node = LogicalOrExpression'2.node

Equivalent to the LogicalOrExpression attributed grammar:

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')?

Clone this wiki locally