---
# System prepended metadata

title: Desdobrar gramática

---

# Desdobrar gramática


A -> B [C] D
| | 
A -> B [C] D

A -> B {C} D
| | 
A -> B (C)* D

A -> A α
A -> β
| |
A -> β R
R -> α R
R -> ε

____________________________________

## Isto é à moda do JJTree

Program -> ImportDeclaration ClassDeclaration EOF

ImportDeclaration -> {"import" Identifier {"." Identifier} ";"}

ClassDeclaration -> "class" Identifier ["extends" Identifier] "{" (VarDeclaration)* (MethodDeclaration)* "}"

VarDeclaration -> Type Identifier ";"

MethodDeclaration -> "public" MD1
MD1 -> Type Identifier "(" [Type Identifier ("," Type Identifier)*] ")" "{" (VarDeclaration)* (Statement)* "return" Expression ";" "}"
MD1 -> "static" "void" "main" "(" "String" "[" "]" Identifier ")" "{" (VarDeclaration)* (Statement)* "}"

Type -> "int" [ "[" "]" ]
Type -> boolean
Type -> Identifier

Statement -> "{" (Statement)* "}"
Statement -> "if" "(" Expression ")" Statement "else" Statement
Statement -> "while" "(" Expression, ")" Statement
Statement -> Expression ";"
Statement -> Identifier [ "[" Expression "]" ] "=" Expression ";"

Expression -> IntegerLiteral Exp1
Expression -> "true" Exp1
Expression -> "false" Exp1
Expression -> Identifier Exp1
Expression -> "this" Exp1
Expression -> "!" Expression Exp1
Expression -> "(" Expression ")" Exp1
Expression -> "new" Exp2
Exp2 -> "int" "[" Expression "]" Exp 1
Exp2 -> Identifier "(" ")" Exp1
Exp1 -> ( ("&&" | "<" | "+" | "-" | "*" | "/") Expression Exp1 )*
Exp1 -> ( "[" Expression "]" Exp1 )    *
Exp1 -> "." Exp3
Exp3 -> "length" Exp1
Exp3 -> Identifier "(" [Expression ("," Expression)*] ")" Exp1


!!!CHECK!!!
Expression -> ( IntegerLiteral | "true" | "false" | Identifier | "this" | ("new" Exp2) | ("!" Expression) | ("(" Expression ")") ) Exp1
Exp1 -> [( ("&&" | "<" | "+" | "-" | "*" | "/") Expression | "[" Expression "]" | "." Exp3 ) Exp1 ]
Exp2 -> ("int" "[" Expression "]") | (Identifier "(" ")")
Exp3 -> "length" | (Identifier "(" [ Expression { "," Expression }] ")")


!NEW!
Expression -> (Term | Variable | Init | Not | EnclosedExpression)

Term -> ( IntegerLiteral | "true" | "false" ) Exp1
Variable -> ( Identifier | "this" ) Exp1
Init -> "new" ( ArrayInit | ObjInit ) Exp1
Not -> "!" Expression Exp1
EnclosedExpression -> "(" Expression ")" Exp1

ArrayInit -> ("int" "[" Expression "]")
ObjInit -> (Identifier "(" ")")


Exp1 -> (BinaryOperation | ArrayAccess | MethodCall)
BinaryOperation -> ("&&" | "<" | "+" | "-" | "*" | "/") Expression Exp1
ArrayAccess -> "[" Expression "]" Exp1
MethodCall -> "." Method Exp1
Exp1 -> ε

Method -> "length"
Method -> Identifier "(" [ Expression { "," Expression }] ")"


____________________________________


## EBNF

Program -> ImportDeclaration ClassDeclaration EOF

ImportDeclaration -> {"import" Identifier {"." Identifier} ";"}

ClassDeclaration -> "class" Identifier ["extends" Identifier] "{" {VarDeclaration} {MethodDeclaration} "}"

VarDeclaration -> Type Identifier ";"

MethodDeclaration -> "public" Type Identifier "(" [Type Identifier {"," Type Identifier}] ")" "{" {VarDeclaration} {Statement} "return" Expression ";" "}"
MethodDeclaration -> "public" "static" "void" "main" "(" "String" "[" "]" Identifier ")" "{" {VarDeclaration} {Statement} "}"

Type -> "int" "[" "]"
Type -> boolean
Type -> int
Type -> Identifier

Statement -> "{" {Statement} "}"
Statement -> "if" "(" Expression ")" Statement "else" Statement
Statement -> "while" "(" Expression, ")" Statement
Statement -> Expression ";"
Statement -> Identifier "=" Expression ";"
Statement -> Identifier "[" Expression "]" "=" Expression ";"

Expression -> Expression ("&&" | "<" | "+" | "-" | "*" | "/") Expression
Expression -> Expression "[" Expression "]"
Expression -> Expression "." "length"
Expression -> Expression "." Identifier "(" [ Expression { "," Expression }] ")"
Expression -> IntegerLiteral
Expression -> "true"
Expression -> "false"
Expression -> Identifier
Expression -> "this"
Expression -> "new" "int" "[" Expression "]"
Expression -> "new" Identifier "(" ")"
Expression -> "!" Expression
Expression -> "(" Expression ")"


____________________________________

## Isto foi à moda do estupido

Program -> ImportDeclaration ClassDeclaration EOF

ImportDeclaration -> "import" Identifier ID1 ";" ImportDeclaration | ε
ID1 -> "." Identifier ID1 | ε

ClassDeclaration -> "class" Identifier CD1 "{" VD MD "}"
CD1 -> "extends" Identifier | ε
VD -> VarDeclaration VD | ε
MD -> MethodDeclaration MD | ε

VarDeclaration -> Type Identifier ";"

MethodDeclaration -> "public" MD1
MD1 -> Type Identifier "(" MD2 ")" "{" VD ST "return" Expression ";" "}"
MD2 -> Type Identifier MD3 | ε
MD3 -> "," Type Identifier MD3 | ε
ST -> Statement ST | ε
MD1 -> "static" "void" "main" "(" "String" "[" "]" Identifier ")" "{" VD ST "}"

Type -> "int" "[" "]"
Type -> boolean
Type -> int
Type -> Identifier

Statement -> "{" ST "}"
Statement -> "if" "(" Expression ")" Statement "else" Statement
Statement -> "while" "(" Expression, ")" Statement
Statement -> Expression ";"
Statement -> Identifier ST2
ST2 -> "=" Expression ";" | "[" Expression "]" "=" Expression ";"

Expression -> IntegerLiteral Exp
Expression -> "true" Exp
Expression -> "false" Exp
Expression -> Identifier Exp
Expression -> "this" Exp
Expression -> "new" Exp2
Exp2 -> "int" "[" Expression "]" Exp 
Exp2 -> Identifier "(" ")" Exp
Expression -> "!" Expression Exp
Expression -> "(" Expression ")" Exp
Exp -> ("&&" | "<" | "+" | "-" | "*" | "/") Expression Exp
Exp -> "[" Expression "]" Exp
Exp -> "." Exp3
Exp3 -> "length" Exp
Exp3 -> Identifier "(" Exp4 ")" Exp
Exp4 -> Expression Exp5 | ε
Exp5 -> "," Expression Exp5 | ε
Exp -> ε


### working with Expression

Expression -> Expression ("&&" | "<" | "+" | "-" | "*" | "/") Expression
Expression -> Expression "[" Expression "]"
Expression -> Expression "." "length"
Expression -> Expression "." Identifier "(" [ Expression { "," Expression }] ")"
Expression -> IntegerLiteral
Expression -> "true"
Expression -> "false"
Expression -> Identifier
Expression -> "this"
Expression -> "new" "int" "[" Expression "]"
Expression -> "new" Identifier "(" ")"
Expression -> "!" Expression
Expression -> "(" Expression ")"



Expression -> RelationalExpression ("&&" RelationalExpression)*
RelationalExpression -> AdditiveExpression ("<" AdditiveExpression)*
AdditiveExpression -> MultiplicativeExpression (("+"|"-") MultiplicativeExpression)*
MultiplicationExpression -> NotExpression (("*"|"/") NotExpression)*
NotExpression -> "!" NotExpression | PrimaryExpression
PrimaryExpression -> PrimaryPrefix (PrimarySuffix)*
PrimaryPrefix -> Literal | "this" | ["."] \<IDENTIFIER\> | "(" Expression ")" | AllocationExpression
PrimarySuffix -> "." "this" | "." AllocationExpression | "[" Expression "]" | "." <IDENTIFIER>
Literal -> <INTEGERLITERAL> | BooleanLiteral
BooleanLiteral -> "true" | "false"
AllocationExpression -> "new" "int" ArrayInit
ArrayInit -> "[" Expression "]"


EnclosedExpression -> "(" Expression ")"
BinaryOperation -> Expression ("&&" | "<" | "+" | "-" | "*" | "/") Expression
ArrayAccess -> Expression "\[" Expression "\]"
MethodCall -> Expression "." ("lengh" | Identifier "(" \[ Expression { "," Expression }\] ")")
Term -> IntegerLiteral | "true" | "false"
Variable -> Identifier | "this"
Initialization -> "new" (("int" "\[" Expression "\]") | (Identifier "(" ")"))
Not -> "!" Expression

---

Q:

void A() : {}
{
  B() (<TOKEN> B())*
}

Como é que podemos anotar a arvore caso o segundo branch exista?

Por exemplo,

void Adição() : {}
{
  Multiplicação() ("+" Multiplicação())*
}

void Multiplicação() : {}
{
  Termo ("\*" Termo)* 
}

Se tivermos 1+2 queremos:
Adição
    Termo
    Termo
    
Mas estamos a obter:
Adição
    Multiplicação
        Termo
    Multiplicação
        Termo
    
A:

void Adição() #void : {}
{
  Multiplicação() ("+" Multiplicação() #Add(2))*
}

void Multiplicação() #void : {}
{
  Termo ("\*" Termo #Mult(2))* 
}


--- 