手动删除左递归算法 [英] Removing Left Recursion Algorithm by Hand

问题描述

我不确定如何完成此语法的左递归清除算法。

  S :: = a B | B S b | S a | S B A | b 
 B :: = S b A | B B | A S B | a 
 D :: = b a | S b 
 A :: = b S A | b | ab 
  

这是我的工作。

 使用顺序S，B，D，A. 
 
 S :: = a BM | B S b M | b M 
 M :: = a M | B A M | ε
 
 B :: = a B M b A | B S b M b A | b M b A | B B | A S B | a 
 
 B :: = a B M b A N | b M b A N | A S B b A N | a N 
 N :: = S b M N | B N |我应该如何从这里进步？
 h2_lin>解决方案
从龙书。 p> 
 
 
根据以下规则：
  A→Aα1| ... | Aαm| β1| ... | βn
  
其中βi是非左递归右侧，写为：
  A→β1A'| ... | βnA'
 A'→α1A'| ... | αmA'| ε
  
要删除所有向左递归，使用此算法，为每个非终端分配一个数字A1 ... An，and：
  for（int i = 1; i <= n; i ++）
 for（int j = 1; j  foreach（Ai→Ajα&& Aj→β1| ... |βn）
替换为Ai→β1α| ... | βnα
从Ai 
中删除向左递归 
 
I'm unsure how to finish the left recursion removal algorithm for this grammar.
S ::= a B | B S b | S a | S B A | b
B ::= S b A | B B | A S B | a
D ::= b a | S b
A ::= b S A | b | a b
Here is my working.
using the order S, B, D, A.

S ::= a B M | B S b M | b M
M ::= a M | B A M | ε

B ::= a B M b A | B S b M b A | b M b A | B B | A S B | a

B ::= a B M b A N | b M b A N | A S B b A N | a N
N ::= S b M N | B N | ε
How should I progress from here?
解决方案
From the Dragon Book.

Given the following rule:
A → Aα1 | ... | Aαm | β1 | ... | βn
where the βi are the non left-recursive right sides, write:
A → β1 A' | ... | βn A'
A' → α1 A' | ... | αm A' | ε
To remove all left-recursion, use this algorithm, assign a number to each non terminal, A1...An, and:
for(int i = 1; i <= n; i++)
    for(int j = 1; j < i; j++)
        foreach(Ai → Ajα && Aj → β1 | ... | βn)
            replace with Ai → β1α |... | βnα
   remove left recursion from Ai


                        
这篇关于手动删除左递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！