Left recursion

Top  Previous  Next

Grammar tests > Left recursion

 

Another possible error of a grammar is the left recursion. The following rule is the simplest example of a left recursion:

 

a = a | B

 

To test this rule leads to an infinite regress. To test a, requires to test a before b and so on. Left recursion is not permitted in TETRA; but there is no automatic test for left recursion.

 

Fortunately left recursion is avoidable. The left recursive rule

:

a = a C | B

 

can be rewritten. Clearly a has to begin with B. On B C can follow and on B C another C can follow. So the formal result is:

 

a = B C *

 

Applied to the first example, C is an empty symbol, with the result:

 

a = B

 

 

Remark:

Productions of the well-known parser generator Yacc frequently are left recursive. For Yacc this is no problem, because it doesn't uses a top down analysis like TETRA, but a bottom up parser. (Because of this Yacc can't manage right recursion.) To translate a Yacc grammar into a TETRA grammar, the rule above helps.

 



This page belongs to the TextTransformer Documentation

Home  Content  German