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