CODEWITHSUNDEEP
recursioncompiler-constructiongrammar
Diogo Soares
Diogo Soares

Reputation: 9

Remove Left Recursion Grammar

How can I remove the left recursions in the following grammar? 

S -> “url” “(“ STRING “)” // basic services
| S “?” S // sequential execution
| S “|” S // concurrent execution
| “timeout” “(“ REAL “,” S “)” // timeout combinator
| “repeat” “(“ S “)” // repetition
| “stall” // nontermination
| “fail” // failure

Upvotes: 0

Views: 81

Answers (1)

Andru Luvisi
Andru Luvisi

Reputation: 25338

The trick is to create a parent production that is right recursive.

T -> S
T -> S "?" T // sequential execution
T -> S "|" T // concurrent execution

S -> “url” “(“ STRING “)” // basic services
| “timeout” “(“ REAL “,” S “)” // timeout combinator
| “repeat” “(“ S “)” // repetition
| “stall” // nontermination
| “fail” // failure

This will recognize the same set of inputs, but beware that T is now right associative, not left associative.

Upvotes: 0

Related Questions