Difference between revisions of "Introduction to Syntax/Exercise 1"

From Wiki**3

< Introduction to Syntax
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 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'''):
 
3. The following grammar selects left associativity for the binary operators ('''and''' and '''or'''):
Line 24: Line 81:
 
  bfactor -> not bfactor | ( bexpr ) | true | false
 
  bfactor -> not bfactor | ( bexpr ) | true | false
  
−
4. The analysis considers the grammar defined in 3.
+
4. The following analysis considers the grammar defined in 3.
 +
 
 +
<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:Compilers]]
 
[[category:Teaching]]
 
[[category:Teaching]]

Revision as of 23:53, 2 April 2010

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.



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.


Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Introduction_to_Syntax/Exercise_1&oldid=3494"