|
|
| (3 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == The Problem ==
| | #REDIRECT [[ist:Introduction to Syntax/Exercise 1]] |
| | |
| Consider the following grammar:
| |
| | |
| bexpr -> bexpr or bexpr | bterm
| |
| bterm -> bterm and bterm | bfactor
| |
| bfactor -> not bfactor | ( bexpr ) | true | false
| |
| | |
| # Identify the terminal and non-terminal symbols of the grammar.
| |
| # Show that the grammar is ambiguous by deriving two different trees for the same input sequence.
| |
| # Write a non-ambiguous grammar for the same language.
| |
| # Build the tree corresponding to the analysis of the following input sequence: '''not ( true or false and true )''' | |
| | |
| == Solution ==
| |
| | |
| 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'''). Terminals are in blue and non-terminals in black.
| |
| | |
| <graph>
| |
| graph nfa {
| |
| node [shape=plaintext]
| |
| 0 [id=0,label="bexpr"];
| |
| 1 [id=1,label="bterm"];
| |
| 2 [id=2,label="bterm"];
| |
| 3 [id=3,label="bterm"];
| |
| 4 [id=4,label="bfactor"];
| |
| 5 [id=5,label="true", fontcolor=blue];
| |
| 6 [id=6,label="and", fontcolor=blue];
| |
| 7 [id=7,label="bterm"];
| |
| 8 [id=8,label="bfactor"];
| |
| 9 [id=9,label="false", fontcolor=blue];
| |
| 10 [id=10,label="and", fontcolor=blue];
| |
| 11 [id=11,label="bterm"];
| |
| 12 [id=12,label="bfactor"];
| |
| 13 [id=13,label="true", fontcolor=blue];
| |
|
| |
| 20 [id=20,label="bexpr"];
| |
| 21 [id=21,label="bterm"];
| |
| 22 [id=22,label="bterm"];
| |
| 23 [id=23,label="bfactor"];
| |
| 24 [id=24,label="true", fontcolor=blue];
| |
| 25 [id=25,label="and", fontcolor=blue];
| |
| 26 [id=26,label="bterm"];
| |
| 27 [id=27,label="bterm"];
| |
| 28 [id=28,label="bfactor"];
| |
| 29 [id=29,label="false", fontcolor=blue];
| |
| 30 [id=30,label="and", fontcolor=blue];
| |
| 31 [id=31,label="bterm"];
| |
| 32 [id=32,label="bfactor"];
| |
| 33 [id=33,label="true", fontcolor=blue];
| |
| | |
| { rank = same; 5; 6; 9; 10; 13; 24; 25; 29; 30; 33 }
| |
| { rank = same; 4; 8; 12; 23; 28; 32 }
| |
| | |
| 0 -- 1
| |
| 1-- 2
| |
| 1-- 10
| |
| 1 -- 11
| |
| 2 -- 3 -- 4 -- 5
| |
| 2 -- 6
| |
| 2 -- 7 -- 8 -- 9
| |
| 11 -- 12 -- 13
| |
| | |
| 20 -- 21
| |
| 21-- 22
| |
| 21-- 25
| |
| 21-- 26
| |
| 22 -- 23 -- 24
| |
| 26 -- 27 -- 28 -- 29
| |
| 26 -- 30
| |
| 26 -- 31 -- 32 -- 33
| |
| }
| |
| </graph>
| |
| | |
| | |
| 3. The following grammar selects left associativity for the binary operators ('''and''' and '''or'''):
| |
| | |
| bexpr -> bexpr or bterm | bterm
| |
| bterm -> bterm and bfactor | bfactor
| |
| bfactor -> not bfactor | ( bexpr ) | true | false
| |
| | |
| 4. The following analysis considers the grammar defined in 3 (again, terminals are in blue and non-terminals in black).
| |
| | |
| <graph>
| |
| graph nfa {
| |
| node [shape=plaintext]
| |
| 0 [id=0,label="bexpr"];
| |
| 1 [id=1,label="bterm"];
| |
| 2 [id=2,label="bfactor"];
| |
| 3 [id=3,label="not",fontcolor=blue];
| |
| 4 [id=4,label="bfactor"];
| |
| 5 [id=5,label="(", fontcolor=blue];
| |
| 6 [id=6,label="bexpr"];
| |
| 7 [id=7,label="bexpr"];
| |
| 8 [id=8,label="bterm"];
| |
| 9 [id=9,label="bfactor"];
| |
| 10 [id=10,label="true", fontcolor=blue];
| |
| 11 [id=11,label="or", fontcolor=blue];
| |
| 12 [id=12,label="bterm"];
| |
| 13 [id=13,label="bterm"];
| |
| 14 [id=14,label="bfactor"];
| |
| 15 [id=15,label="false", fontcolor=blue];
| |
| 16 [id=16,label="and", fontcolor=blue];
| |
| 17 [id=17,label="bfactor"];
| |
| 18 [id=18,label="true", fontcolor=blue];
| |
| 19 [id=19,label=")", fontcolor=blue];
| |
| | |
| { rank = same; 3; 5; 10; 11; 15; 16; 18; 19 }
| |
| { rank = same; 9; 14; 17 }
| |
| | |
| 0 -- 1 -- 2
| |
| 2 -- 3
| |
| 2 -- 4
| |
| 4 -- 5
| |
| 4 -- 6
| |
| | |
| 6 -- 7 -- 8 -- 9 -- 10
| |
| 6 -- 11
| |
| 6 -- 12
| |
| 12 -- 13 -- 14 -- 15
| |
| 12 -- 16
| |
| 12 -- 17 -- 18
| |
| | |
| 4 -- 19
| |
| }
| |
| </graph>
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |