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