(4 intermediate revisions by the same user not shown) | |||
Line 3: | Line 3: | ||
Consider the following grammar: | Consider the following grammar: | ||
− | + | E -> E <font color="blue">'''or'''</font> E | T | |
− | + | T -> T <font color="blue">'''and'''</font> T | F | |
− | + | F -> <font color="blue">'''not'''</font> F | <font color="blue">'''('''</font> E <font color="blue">''')'''</font> | <font color="blue">'''true'''</font> | <font color="blue">'''false'''</font> | |
# Identify the terminal and non-terminal symbols of the grammar. | # Identify the terminal and non-terminal symbols of the grammar. | ||
Line 16: | Line 16: | ||
1. The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''. | 1. The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''. | ||
− | 2. The following trees are possible for '''true and false and true''' (an analogous analysis could be done for '''or'''). | + | 2. The following two trees are possible for '''true and false and true''' (an analogous analysis could be done for '''or'''). The fact that more than one tree can be found (independently of the method used), is a signal that the grammar is ambiguous. In the case shown, the ambiguity manifests itself in the associativity of the '''and''' operator (similar finding can be shown for '''or''' -- this is left as an exercise). In the trees, terminal symbols (a.k.a. tokens) are in blue and non-terminal symbols are in black. |
− | < | + | <dot-hack> |
graph nfa { | graph nfa { | ||
node [shape=plaintext] | node [shape=plaintext] | ||
− | 0 [id=0,label=" | + | 0 [id=0,label="E"]; |
− | 1 [id=1,label=" | + | 1 [id=1,label="T"]; |
− | 2 [id=2,label=" | + | 2 [id=2,label="T"]; |
− | 3 [id=3,label=" | + | 3 [id=3,label="T"]; |
− | 4 [id=4,label=" | + | 4 [id=4,label="F"]; |
5 [id=5,label="true", fontcolor=blue]; | 5 [id=5,label="true", fontcolor=blue]; | ||
6 [id=6,label="and", fontcolor=blue]; | 6 [id=6,label="and", fontcolor=blue]; | ||
− | 7 [id=7,label=" | + | 7 [id=7,label="T"]; |
− | 8 [id=8,label=" | + | 8 [id=8,label="F"]; |
9 [id=9,label="false", fontcolor=blue]; | 9 [id=9,label="false", fontcolor=blue]; | ||
10 [id=10,label="and", fontcolor=blue]; | 10 [id=10,label="and", fontcolor=blue]; | ||
− | 11 [id=11,label=" | + | 11 [id=11,label="T"]; |
− | 12 [id=12,label=" | + | 12 [id=12,label="F"]; |
13 [id=13,label="true", fontcolor=blue]; | 13 [id=13,label="true", fontcolor=blue]; | ||
− | 20 [id=20,label=" | + | 20 [id=20,label="E"]; |
− | 21 [id=21,label=" | + | 21 [id=21,label="T"]; |
− | 22 [id=22,label=" | + | 22 [id=22,label="T"]; |
− | 23 [id=23,label=" | + | 23 [id=23,label="F"]; |
24 [id=24,label="true", fontcolor=blue]; | 24 [id=24,label="true", fontcolor=blue]; | ||
25 [id=25,label="and", fontcolor=blue]; | 25 [id=25,label="and", fontcolor=blue]; | ||
− | 26 [id=26,label=" | + | 26 [id=26,label="T"]; |
− | 27 [id=27,label=" | + | 27 [id=27,label="T"]; |
− | 28 [id=28,label=" | + | 28 [id=28,label="F"]; |
29 [id=29,label="false", fontcolor=blue]; | 29 [id=29,label="false", fontcolor=blue]; | ||
30 [id=30,label="and", fontcolor=blue]; | 30 [id=30,label="and", fontcolor=blue]; | ||
− | 31 [id=31,label=" | + | 31 [id=31,label="T"]; |
− | 32 [id=32,label=" | + | 32 [id=32,label="F"]; |
33 [id=33,label="true", fontcolor=blue]; | 33 [id=33,label="true", fontcolor=blue]; | ||
Line 72: | Line 72: | ||
26 -- 31 -- 32 -- 33 | 26 -- 31 -- 32 -- 33 | ||
} | } | ||
− | </ | + | </dot-hack> |
− | 3. The following grammar selects left associativity for the binary operators ('''and''' and '''or'''): | + | 3. To solve the problem found before, a grammar can be written that only accepts one direction for the associativity of the two binary operators present. The following rewritten grammar selects left associativity for the binary operators ('''and''' and '''or'''): |
− | + | E -> E <font color="blue">'''or'''</font> T | T | |
− | + | T -> T <font color="blue">'''and'''</font> F | F | |
− | + | F -> <font color="blue">'''not'''</font> F | <font color="blue">'''('''</font> E <font color="blue">''')'''</font> | <font color="blue">'''true'''</font> | <font color="blue">'''false'''</font> | |
− | 4. The following analysis considers the grammar defined in 3. | + | 4. The following analysis considers the grammar defined in 3 (again, terminals are in blue and non-terminals in black). |
− | < | + | <dot-hack> |
graph nfa { | graph nfa { | ||
node [shape=plaintext] | node [shape=plaintext] | ||
− | 0 [id=0,label=" | + | 0 [id=0,label="E"]; |
− | 1 [id=1,label=" | + | 1 [id=1,label="T"]; |
− | 2 [id=2,label=" | + | 2 [id=2,label="F"]; |
3 [id=3,label="not",fontcolor=blue]; | 3 [id=3,label="not",fontcolor=blue]; | ||
− | 4 [id=4,label=" | + | 4 [id=4,label="F"]; |
5 [id=5,label="(", fontcolor=blue]; | 5 [id=5,label="(", fontcolor=blue]; | ||
− | 6 [id=6,label=" | + | 6 [id=6,label="E"]; |
− | 7 [id=7,label=" | + | 7 [id=7,label="E"]; |
− | 8 [id=8,label=" | + | 8 [id=8,label="T"]; |
− | 9 [id=9,label=" | + | 9 [id=9,label="F"]; |
10 [id=10,label="true", fontcolor=blue]; | 10 [id=10,label="true", fontcolor=blue]; | ||
11 [id=11,label="or", fontcolor=blue]; | 11 [id=11,label="or", fontcolor=blue]; | ||
− | 12 [id=12,label=" | + | 12 [id=12,label="T"]; |
− | 13 [id=13,label=" | + | 13 [id=13,label="T"]; |
− | 14 [id=14,label=" | + | 14 [id=14,label="F"]; |
15 [id=15,label="false", fontcolor=blue]; | 15 [id=15,label="false", fontcolor=blue]; | ||
16 [id=16,label="and", fontcolor=blue]; | 16 [id=16,label="and", fontcolor=blue]; | ||
− | 17 [id=17,label=" | + | 17 [id=17,label="F"]; |
18 [id=18,label="true", fontcolor=blue]; | 18 [id=18,label="true", fontcolor=blue]; | ||
19 [id=19,label=")", fontcolor=blue]; | 19 [id=19,label=")", fontcolor=blue]; | ||
Line 125: | Line 125: | ||
4 -- 19 | 4 -- 19 | ||
} | } | ||
− | </ | + | </dot-hack> |
− | [[category: | + | [[category:Compiladores]] |
− | [[category: | + | [[category:Ensino]] |
Consider the following grammar:
E -> E or E | T T -> T and T | F F -> not F | ( E ) | true | false
1. The terminal symbols are all the symbols not defined by a rule: or, and, not, (, ), true, false.
2. The following two trees are possible for true and false and true (an analogous analysis could be done for or). The fact that more than one tree can be found (independently of the method used), is a signal that the grammar is ambiguous. In the case shown, the ambiguity manifests itself in the associativity of the and operator (similar finding can be shown for or -- this is left as an exercise). In the trees, terminal symbols (a.k.a. tokens) are in blue and non-terminal symbols are in black.
3. To solve the problem found before, a grammar can be written that only accepts one direction for the associativity of the two binary operators present. The following rewritten grammar selects left associativity for the binary operators (and and or):
E -> E or T | T T -> T and F | F F -> not F | ( E ) | true | false
4. The following analysis considers the grammar defined in 3 (again, terminals are in blue and non-terminals in black).