Exercise 1 All the grammar presented below are possible solutions, other grammars might be good solutions as well.
<Identifier> ::= <Letter> <String> <String> ::= <empty> | <Letter> <String> | <Digit> <String> <Digit> ::= 0 | <NonZeroDigit> <NonZeroDigit> ::= 1 | 2 | ... | 8 | 9 <Letter> ::= a | b | ... | y | zComment: if you have considered capital letters instead, or both, is fine as well.
<NaturalNum> ::= <NonZeroDigit> <DigitString> <DigitString> ::= <empty> | <Digit> <DigitString> <Digit> ::= 0 | <NonZeroDigit> <NonZeroDigit> ::= 1 | 2 | ... | 8 | 9
<RealNum> ::= .<Fraction> | <Integer>. | <Integer>.<Fraction> <Integer> ::= <Digit> | <NonZeroDigit> <DigitString> <Fraction> ::= <Digit> | <Digit> <DigitString> <DigitString> ::= <empty> | <Digit> DigitString> <Digit> ::= 0 | <NonZeroDigit> <NonZeroDigit> ::= 1 | 2 | ... | 8 | 9Comment: This grammar does not generate numbers like 01.12. However it geneartes numbers like 1.00. There was no precise specification in the text about the 0's, hence difefrent solutions on this regard are possible.
Exercise 2
<Formula> ::= exitsts <Ide>. <Formula> | forall <Ide>. <Formula> | <F1> <F1> ::= <F2> implies <F1> | <F2> <F2> ::= <F2> or <F3> | <F3> <F3> ::= <F3> and <F4> | <F4> <F4> ::= not <F4> | <Atom>
Exercise 3 There are 2 kind of ambiguities due to the definition of this grammar.
Cmd Cmd / | \ / | \ Cmd ; Cmd Cmd ; Cmd / / | | | | \ \ Cmd ; Cmd print(3) print(1) Cmd ; Cmd | | | | print(1) print(2) print(2) print(3)This kind of ambiguity is not relevant semantically because ";" is associative.
Cmd Cmd __________|___________ / | \ | | | | | | Cmd ; Cmd if Exp then Cmd else Cmd ________________|___ | / / | \ | | | | | | print(3) print(1) Cmd; Cmd if Exp then Cmd else Cmd | | | | print(2) print(3) print(1) print(2)This ambiguity is relevant at semantical level becuase if the statement print(3) is inside the else then will be executed only if the condition is true, otherwise will always be executed (after the conditional statement).
Exercise 4
a. b. E E / | \ | E + T T | | | T F F | | / | \ F num ( E ) | | / | \ num 3 E + T | | T F | | F num | | num 3 | 2 c. d. E E / | \ | E + T T | / | \ / | \ T T * F T * F | | | | | F F num F num | | | / | \ | num num 5 ( E ) 5 | | / | \ 2 3 E + T | | T F | | F num | | num 3 e. | 2 E / | \ E + T | | T F | | / | \ F ( E ) | | num T | / | \ 2 T * F | | F num | | num 5 | 3
Exercise 8
Type ::= CType -> Type | CType CType ::= CType * TVar | TVar
Exercise 10
Declaration ____ Declaration ____ / \ \ / \ \ Type Declarator ; Type Declarator ; / | \ / / | | \ int * Declarator _ int Declarator [ number ] / | | \ / \ Declarator [ number ] * Declarator | | name name
<Declaration> ::= <Type><Declarator> ; <Type> ::= int | char <Declarator> ::= * <Declarator> | <Decl> <Decl> ::= <Decl> '[' number ']' | <Decl> '(' Type ')' | '(' <Declarator> ')' | nameComments: there is a penalty if you change the language generated by your grammar.
Exercise 12
S ::= lambda | a | b | c | ... | z | aSa | bSb | cSc | ... | zSzwhere lambda stands for the empty string.