COMP360 Programming Languages
Exam 3 Study Guide
The third COMP360 exam will have
questions similar to these.
Write a Recursive Descent parsing functions for the following grammar where <var> is a variable token produced by a previous lexical scan.
<A> ::= { <B> , <A> } |
<B>
<B> ::= ( <A> ) | <C>
<C> ::= x | y | z
void lex() { // this reads the
next token
}
void A() { // <A>
::= { <B> , <A> } | <B>
if (token == ‘{‘ )
{
lex(); // you need to call lex after validating
each terminal symbol
B();
if (token !=
‘,’) error();
lex();
A();
if (token !=
‘}’) error();
lex();
} else {
B();
}
}
void B() { // <B> ::= ( <A> ) | <C>
if (token == ‘(‘ )
{
lex();
A();
if (token !=
‘)’) error();
lex();
} else {
C();
}
}
void C() { // <C> ::= x | y | z
if (token == ‘x‘ )
|| (token == ‘y’)
|| (token == ‘z’) {
lex();
} else {
error();
}
}
Is the above grammar in Chomsky Normal Form? No, Chomsky Normal
Form grammars are always in the form <A> ::=
x or <A> ::= <B><C>
Is the above grammar in Greibach Normal Form? No, all rules in Greibach
Normal Form grammars start with a terminal symbol.
Draw a finite state automaton that recognizes decimal numbers that are evenly divisible by 5.
From the DFA created in the above example, write the transition table for a lexical scanner.
|
|
State 0 |
State 1 |
|
0 , 5 |
0 |
0 |
|
1 – 4, 6 - 9 |
1 |
1 |
Consider the following BNF grammar rules
<A> ::= { <B> , <A> } |
<B>
<B> ::= ( <A> ) | <C>
<C> ::= x | y | z
Indicate if the following strings are members of this language (You
could compile the above program and enter the examples to be sure.)
yes x
yes { x , y}
yes ( z )
no {x}
no x , y
no <B> non-terminals are never members of the language
no {{x , z} , y }
yes { x , {y , z} }
Prove that the following grammar is ambiguous. (This grammar creates properly nested parenthesis.)
S
::= SS | (S) | ( )
A grammar is ambiguous if there
exists more than one parse tree for the same input string. Consider the input string “( ) ( ) ( )” which has the two following parse trees.
What is Greibach Normal Form and why is it useful?
All rules in Greibach Normal Form
grammars start with a terminal symbol.
This makes it much easier for top down parsing techniques, such as
recursive descent, to determine which production is to be applied.