1# -*- coding: utf-8 -*- 2# Copyright (C) 2017 by Juancarlo Añez 3# Copyright (C) 2012-2016 by Juancarlo Añez and Thomas Bragg 4from __future__ import absolute_import, division, print_function, unicode_literals 5 6import unittest 7 8from grako.exceptions import FailedParse 9from grako.tool import compile 10 11 12class LeftRecursionTests(unittest.TestCase): 13 14 def test_direct_left_recursion(self, trace=False): 15 grammar = ''' 16 @@left_recursion :: True 17 start 18 = 19 expre $ 20 ; 21 22 expre 23 = 24 expre '+' number 25 | 26 expre '*' number 27 | 28 number 29 ; 30 31 number 32 = 33 ?/[0-9]+/? 34 ; 35 ''' 36 model = compile(grammar, "test") 37 ast = model.parse("1*2+3*5", trace=trace, colorize=True) 38 self.assertEqual(['1', '*', '2', '+', '3', '*', '5'], ast) 39 40 def test_indirect_left_recursion(self, trace=False): 41 grammar = ''' 42 @@left_recursion :: True 43 start = x $ ; 44 x = expr ; 45 expr = x '-' num | num; 46 num = ?/[0-9]+/? ; 47 ''' 48 model = compile(grammar, "test") 49 ast = model.parse("5-87-32", trace=trace, colorize=True) 50 self.assertEqual(['5', '-', '87', '-', '32'], ast) 51 52 def test_indirect_left_recursion_with_cut(self, trace=False): 53 grammar = ''' 54 @@left_recursion :: True 55 start = x $ ; 56 x = expr ; 57 expr = x '-' ~ num | num; 58 num = ?/[0-9]+/? ; 59 ''' 60 model = compile(grammar, "test") 61 ast = model.parse("5-87-32", trace=trace, colorize=True) 62 self.assertEqual(['5', '-', '87', '-', '32'], ast) 63 64 def test_indirect_left_recursion_complex(self, trace=False): 65 grammar = ''' 66 @@left_recursion :: True 67 start = Primary $ ; 68 Primary = PrimaryNoNewArray ; 69 70 PrimaryNoNewArray = 71 ClassInstanceCreationExpression 72 | MethodInvocation 73 | FieldAccess 74 | ArrayAccess 75 | 'this' ; 76 77 ClassInstanceCreationExpression = 78 'new' ClassOrInterfaceType '(' ')' 79 | Primary '.new' Identifier '()' ; 80 81 MethodInvocation = 82 Primary '.' MethodName '()' 83 | MethodName '()' ; 84 85 FieldAccess = 86 Primary '.' Identifier 87 | 'super.' Identifier ; 88 89 ArrayAccess = 90 Primary '[' Expression ']' 91 | ExpressionName '[' Expression ']' ; 92 93 ClassOrInterfaceType = 94 ClassName 95 | InterfaceTypeName ; 96 97 ClassName = 'C' | 'D' ; 98 InterfaceTypeName = 'I' | 'J' ; 99 Identifier = 'x' | 'y' | ClassOrInterfaceType ; 100 MethodName = 'm' | 'n' ; 101 ExpressionName = Identifier ; 102 Expression = 'i' | 'j' ; 103 ''' 104 model = compile(grammar, "test") 105 ast = model.parse("this", trace=trace, colorize=True) 106 self.assertEqual('this', ast) 107 ast = model.parse("this.x", trace=trace, colorize=True) 108 self.assertEqual(['this', '.', 'x'], ast) 109 ast = model.parse("this.x.y", trace=trace, colorize=True) 110 self.assertEqual(['this', '.', 'x', '.', 'y'], ast) 111 ast = model.parse("this.x.m()", trace=trace, colorize=True) 112 self.assertEqual(['this', '.', 'x', '.', 'm', '()'], ast) 113 ast = model.parse("x[i][j].y", trace=trace, colorize=True) 114 self.assertEqual(['x', '[', 'i', ']', '[', 'j', ']', '.', 'y'], ast) 115 116 def test_no_left_recursion(self, trace=False): 117 grammar = ''' 118 @@left_recursion :: True 119 start 120 = 121 expre $ 122 ; 123 124 expre 125 = 126 expre '+' number 127 | 128 expre '*' number 129 | 130 number 131 ; 132 133 number 134 = 135 ?/[0-9]+/? 136 ; 137 ''' 138 model = compile(grammar, "test") 139 model.parse("1*2+3*5", trace=trace, colorize=True) 140 try: 141 model.parse("1*2+3*5", left_recursion=False, trace=trace, colorize=True) 142 self.Fail('expected left recursion failure') 143 except FailedParse: 144 pass 145 146 def test_nested_left_recursion(self, trace=False): 147 grammar_a = ''' 148 @@left_recursion :: True 149 s = e $ ; 150 e = [e '+'] t ; 151 t = [t '*'] a ; 152 a = ?/[0-9]/? ; 153 ''' 154 grammar_b = ''' 155 @@left_recursion :: True 156 s = e $ ; 157 e = [e '+'] a ; 158 a = n | p ; 159 n = ?/[0-9]/? ; 160 p = '(' @:e ')' ; 161 ''' 162 model_a = compile(grammar_a, "test") 163 model_b = compile(grammar_b, "test") 164 ast = model_a.parse("1*2+3*4", trace=trace, colorize=True) 165 self.assertEqual(['1', '*', '2', '+', ['3', '*', '4']], ast) 166 ast = model_b.parse("(1+2)+(3+4)", trace=trace, colorize=True) 167 self.assertEqual(['1', '+', '2', '+', ['3', '+', '4']], ast) 168 ast = model_a.parse("1*2*3", trace=trace, colorize=True) 169 self.assertEqual(['1', '*', '2', '*', '3'], ast) 170 ast = model_b.parse("(((1+2)))", trace=trace, colorize=True) 171 self.assertEqual(['1', '+', '2'], ast) 172 173 def notest_left_recursion_bug(self, trace=False): 174 grammar = '''\ 175 @@grammar :: Minus 176 @@left_recursion :: True 177 178 start = expression $ ; 179 180 expression = 181 | paren_expression 182 | minus_expression 183 | value 184 ; 185 186 paren_expression 187 = 188 '(' expression ')' 189 ; 190 191 minus_expression 192 = 193 expression '-' value 194 ; 195 196 value = /[0-9]+/ ; 197 ''' 198 model = compile(grammar=grammar) 199 # model.parse('3', trace=trace, colorize=True) 200 # model.parse('3 - 2', trace=trace, colorize=True) 201 # model.parse('(3 - 2)', trace=trace, colorize=True) 202 # model.parse('(3 - 2) - 1', trace=trace, colorize=True) 203 # model.parse('3 - 2 - 1', trace=trace, colorize=True) 204 model.parse('3 - (2 - 1)', trace=trace, colorize=True) 205 206 207def main(trace=True): 208 t = LeftRecursionTests('test_direct_left_recursion') 209 # t.test_direct_left_recursion(trace=trace) 210 # t.test_indirect_left_recursion(trace=trace) 211 # t.test_indirect_left_recursion_with_cut(trace=trace) 212 # t.test_indirect_left_recursion_complex(trace=trace) 213 # t.test_no_left_recursion(trace=trace) 214 # t.test_nested_left_recursion(trace=trace) 215 t.no_test_left_recursion_bug(trace=trace) 216 217 218if __name__ == '__main__': 219 main() 220