Introduction to Syntax/Exercise 1

The Problem

Consider the following grammar:

 bexpr   -> bexpr or bexpr | bterm
 bterm   -> bterm and bterm | bfactor
 bfactor -> not bfactor | ( bexpr ) | true | false

1. Identify the terminal and non-terminal symbols of the grammar.
2. Show that the grammar is ambiguous by deriving two different trees for the same input sequence.
3. Write a non-ambiguous grammar for the same language.
4. 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: or, and, not, (, ), true, false.

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>