Discussion Session 4¶

Assignment 2¶

Grammar with ambiguity:

formula ::=  formula Xor formula
formula ::=  base
base    ::=  T
base    ::=  F


After left-recursion elimination:

formula  ::=  base formula2    // Atom
formula2 ::=  Xor formula formula2  // Xor
formula2 ::=                      // Empty
base     ::=  T
base     ::=  F


The grammar still has ambiguity, but we can use recursive descent parsing technique now.

Discussion

What is the abstract syntax for T Xor F Xor T?

Grammar without ambiguity:

formula ::=  formula Xor base
formula ::=  base
base    ::=  T
base    ::=  F


After left-recursion elimination:

formula  ::=  base formula2    // Atom
formula2 ::=  Xor base formula2 // Xor
formula2 ::=                      // Empty
base     ::=  T
base     ::=  F


Discussion

What is the abstract syntax for T Xor F Xor T?

Note

Recursive descendent parsing cannot handling left associative. Left-recursion elimination leads to right associativity. We have to convert the generated abstract syntax into left associativity.

Going still further

formula ::=  base Xor formula
formula ::=  base
base    ::=  T
base    ::=  F


Discussion

What is the abstract syntax for T Xor F Xor T?

Example of unittest¶

test.py

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 import unittest from parse import * class ExpressionTestCase(unittest.TestCase): def test_01(self): s = ["a", "xor", "b"] t = {'Xor': [ \ {'Variable': ['a']}, \ {'Variable': ['b']} ]} self.assertEqual(t, expression(s)[0]) class NumberTestCase(unittest.TestCase): def test_1(self): self.assertEqual(123, number(["123"])[0]) def test_negtive(self): self.assertEqual(-123, number(["-123"])[0]) def test_zero(self): self.assertEqual(0, number(["0"])[0]) class VariableTestCase(unittest.TestCase): def test_1(self): s = "abc" self.assertEqual(s, variable([s])[0]) def test_2(self): s = "aAdfe1" self.assertEqual(s, variable([s])[0]) def test_3(self): s = "A" self.assertEqual(None, variable([s])) class FormulaTestCase(unittest.TestCase): def test_left_asso(self): s = ["x", "xor", "true", "xor", "y"] t = {"Xor": [{"Xor": [{"Variable": ["x"]}, "True"]}, {"Variable": ["y"]}]} self.assertEqual(t, formula(s)[0]) def test_invalid(self): s = ["x", "xor", "true", "xor", "y", "3"] t = {"Xor": [{"Xor": [{"Variable": ["x"]}, "True"]}, {"Variable": ["y"]}]} self.assertEqual(None, formula(s)) class FactorTestCase(unittest.TestCase): def test_left_asso(self): s = ["x", "*", "1", "*", "y"] t = {"Mult": [{"Mult": [{"Variable": ["x"]}, {"Number": [1]}]}, {"Variable": ["y"]}]} self.assertEqual(t, factor(s)[0]) def test_invalid(self): s = ["x", "*", "1", "*", "y", "0"] t = {"Mult": [{"Mult": [{"Variable": ["x"]}, {"Number": [1]}]}, {"Variable": ["y"]}]} self.assertEqual(None, factor(s)) class TermTestCase(unittest.TestCase): def test_add(self): s = ["x", "+", "1"] t = {"Plus": [{"Variable": ["x"]}, {"Number": [1]}]} self.assertEqual(t, term(s)[0]) def test_mul(self): s = ["x", "*", "1"] t = {"Mult": [{"Variable": ["x"]}, {"Number": [1]}]} self.assertEqual(t, term(s)[0]) # def test_div(self): # s = ["x", "/", "1"] # t = {"Div": [{"Variable": ["x"]}, {"Number": [1]}]} # self.assertEqual(t, term(s)[0]) def test_eq(self): s = ["x", "==", "1"] t = {"Eq": [{"Variable": ["x"]}, {"Number": [1]}]} self.assertEqual(t, term(s)[0]) def test_lessthan(self): s = ["x", "<", "1"] t = {"LessThan": [{"Variable": ["x"]}, {"Number": [1]}]} self.assertEqual(t, term(s)[0]) def test_right_asso(self): s = ["x", "+", "1", "+", "y"] t = {"Plus": [{"Variable": ["x"]}, {"Plus": [{"Number": [1]}, {"Variable": ["y"]}]}]} self.assertEqual(t, term(s)[0]) def test_invalid(self): s = ["x", "+", "1", "+", "y", "0"] t = {"Plus": [{"Variable": ["x"]}, {"Plus": [{"Number": [1]}, {"Variable": ["y"]}]}]} self.assertEqual(None, term(s)) class ProgramTestCase(unittest.TestCase): def test_if(self): s = ["if", "1", "<", "x", "{", \ "print", "x", "+", "y", ";", "print", "false", ";", \ "}", \ "print", "true", "xor", "false", ";", "print", "1", ";", \ ] t = {"If": [ \ {"LessThan": [ \ {"Number": [1]}, \ {"Variable": ["x"]} \ ]}, \ {"Print": [ \ {"Plus": [ \ {"Variable": ["x"]}, \ {"Variable": ["y"]} \ ]}, \ {"Print": [ \ "False", \ "End" \ ]} \ ]}, \ {"Print": [ \ {"Xor": ["True", "False"]}, \ {"Print": [ \ {"Number": [1]}, "End" \ ]} \ ]} \ ]} self.assertEqual(t, program(s)[0]) def test_02(self): s = "assign x := 1 + 2 ; while false { assign y := a xor b ; }".split(" ") t = {'Assign': [ \ {'Variable': ['x']}, \ {'Plus': [ \ {'Number': [1]}, \ {'Number': [2]} \ ]}, \ {'While': [ \ 'False', \ {'Assign': [ \ {'Variable': ['y']}, \ {'Xor': [ \ {'Variable': ['a']}, \ {'Variable': ['b']} \ ]}, \ 'End' \ ]}, \ 'End' \ ]} \ ]} self.assertEqual(t, program(s)[0]) def test_03(self): s = "if false { assign y := a xor b ; }".split(" ") t = {'If': [ \ 'False', \ {'Assign': [ \ {'Variable': ['y']}, \ {'Xor': [ \ {'Variable': ['a']}, \ {'Variable': ['b']} \ ]}, \ 'End' \ ]}, \ 'End' \ ]} self.assertEqual(t, program(s)[0]) def test_04(self): s = "assign y := a xor b ;".split(" ") t = {'Assign': [ \ {'Variable': ['y']}, \ {'Xor': [ \ {'Variable': ['a']}, \ {'Variable': ['b']} \ ]}, \ 'End' \ ]} self.assertEqual(t, program(s)[0]) class TokenizeTestCase(unittest.TestCase): def test_1(self): x = "if 1 < x {" \ "print x + y; print false;" \ "}" \ "print true xor false; print 1;" s = ["if", "1", "<", "x", "{", \ "print", "x", "+", "y", ";", "print", "false", ";", \ "}", \ "print", "true", "xor", "false", ";", "print", "1", ";", \ ] self.assertEqual(s, tokenize(x)) # def getTestSuite(): # tloader = unittest.TestLoader() # suite1 = tloader.loadTestsFromTestCase(NumberTestCase) # suite2 = tloader.loadTestsFromTestCase(VariableTestCase) # # suite = unittest.TestSuite() # suite.addTest(suite1) # suite.addTest(suite2) # return suite # # def main(): # runner = unittest.TextTestRunner() # runner.run(getTestSuite()) # # # if __name__ == '__main__': # main() 

Unit Testing (only for Python 3):

python3 -m unittest test  # all the tests in test.py
python3 -m unittest test.NumberTestCase  # all the tests in NumberTestCase
python3 -m unittest test.NumberTestCase.test_negtive # one test


Operator Precedence and Associativity¶

start  ::=  term2               // lowest precedence
term2  ::=  term2 Opr2a term1  // left associative
term2  ::=  term2 Opr2b term1  // left associative
term2  ::=  term1               // next precedence
term1  ::=  term Opr1 term1   // right associative
term1  ::=  term                // next precedence
term   ::=  factor + term      // right associative
term   ::=  factor               // next precedence
factor ::=  factor * base     // left associative
factor ::=  base               // next precedence
base   ::=  - base
base   ::=  log (term2)
base   ::=  (term2)
base   ::=  Variable
base   ::=  Number
`
1. Operator Precedence: The lower in the grammar, the higher the precedence.
2. Operator Associativity:
• Tie breaker for precedence

• Left recursion in the grammar means

• left associativity of the operator
• left branch in the tree
• Right recursion in the grammar means

• Right associativity of the operator
• Right branch in the tree