CS 320 : Formal Grammars
Marco Gaboardi MSC 116 gaboardi@bu.edu
Announcements
• Thirdtheoryassignmentpostedsoon.
From previous classes…
BNF – Backus Normal/Naur Form
• A grammar is defined by a set of terminals (tokens), a set of nonterminals, a designated nonterminal start symbol, and a finite nonempty set of rules
::=
::= a | an | the
::= man | apple | worm | penguin ::=
Generator vs Recognizer
::= a | b | c | d
Recognize a sentence Generate a sentence
a = b + const
= b + const = + const =
=
a =
a =
a = b + const
Some of the challenges:
• There is a (potentially) infinite number of source programs that we need to recognize.
§ An infinity of words
§ An infinity of sentences
• There should be no ambiguity in the way the program is
interpreted.
§ Unique vocabulary,
§ Uniquely determine sentences
• The source program may contain syntax errors and the
compiler/interpreter has to recognize them.
§ Lexical errors (errors in the choice of words)
§ Grammatical errors (errors in the construction of sentences)
Parse Tree
•A parse tree is a hierarchical
representation of a derivation
We can represent it with the following hierarchical structure (parse tree)
Suppose we have the following derivation
=>
=> =
=> a =
=> a =
=> a = +
=> a = b +
=> a = b + const
= a
b
const
Ambiguous Grammars
•A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse trees.
2+3*4
+
2+3*4
2
Plan for today
Disambiguate ambigous grammars
How can we avoid ambiguity?
How can we disambiguate between the two parse trees for the following expression?
2+3+4
+
24
3423
How can we avoid ambiguity?
How can we disambiguate between the two parse trees for the following expression?
2+3+4
First idea: make the parentheses part of the language
((2+3)+4) (2+(3+4) One way to do this is to change the grammar:
We need to add them everywhere!
We add parentheses around every expression
How can we avoid ambiguity and preserve the structure of the grammar?
Second idea: If we use the parse tree to indicate precedence levels of the operators, we cannot have ambiguity.
+
2
Problem: it requires to work directly with parse trees.
How can we avoid ambiguity and preserve the structure of the grammar?
Why is the previous grammar ambiguous?
2+3*4
Two “classes” of operations that have different precedence and the grammar does not distinguish them.
2+3+4
Two “occurrences” of the same operations have the same precedence and the grammar does not distinguish them.
Dealing with associativity?
2+3+4
Two “occurrences” of the same operations have the same precedence and the grammar does not distinguish them.
+
34
+
2
We need to break the symmetry and commit to one choice.
4
Dealing with associativity?
How can we derive the following expression?
2+3+4+5
We modify recursion to break the symmetry
=>
=>
=>
=> 2 +
=> 2 + 3
=> 2 + 3 +
=> 2 + 3 + 4
=> 2 + 3 + 4 +
=> 2 + 3 + 4 + 5
Dealing with associativity?
How can we recognize the following expression?
2+3+4+5
We modify recursion to break the symmetry
Associativity by Grammar Design
+
Left-associative
4
+3 2
Right-associative
Left-recursive
2
+
3
Right-recursive
4
Associativity by Grammar Design
Ambiguous Unambiguous
TopHat Q1-Q5
Some examples
Design an equivalent grammar which is unambiguous and right associative.
Some examples
Design an equivalent grammar which is unambiguous and left associative.
Dealing with precedence?
2+3*4
Two “classes” of operations that have different precedence and the grammar does not distinguish them.
+
34
*
2
Again: We need to break the symmetry and commit to one choice.
4
Dealing with precedence?
2+3*4
How can we derive the following expression?
We use two nonterminal to break the symmetry
=>
=> 2 +
=> 2 +
=> 2 + 3 *
=> 2 + 3 * 4
Dealing with precedence?
2+3*4
How can we recognize the following expression?
We use two nonterminal to break the symmetry
Some examples
Design an equivalent grammar which is unambiguous and give precedence to * over ->.
Some examples
Design an equivalent grammar which is unambiguous and give precedence to # over $.
Dealing with precedence?
Can we derive the following expression?
(2+3)*4
We use two nonterminal to break the symmetry
Recovering general expressions
Can we derive the following expression?
(2+3)*4
We need to introduce parentheses.
Dealing with precedence?
Can we derive the following expression?
(2+3)*4
=>
=>
=> (
=> (
=> ( 2 +
=> ( 2 + 3 )
=> ( 2 + 3 ) *
=> ( 2 + 3 ) * 4
Putting everything together
Is this grammar still ambiguous?
No magic wand, we have to determine whether we can build two parse trees for the same expression. So, we need to look at the parse trees corresponding to its derivations.
Some examples
Design an equivalent unambigous grammar which is right associative on ::, which gives precedence to ; over @, and which allow to use begin … end to delimit programs with different precedence.
Some examples
Design an equivalent unambigous grammar which is right associative on ::, which gives precedence to ; over @, and which allow to use begin … end to delimit programs with different precedence.
::= x | y | z
TopHat Q8-Q13