对于 LR 解析器,FIRST 集定义如下(来源):
FIRST(A) 是可以作为匹配非终结符 A 的任何规则链的第一个元素出现的终结符集合。
现在给定一个 CFG,(I)不允许空产生(即没有规则是 format X → ε
)并且(II)是正确的(即没有符号自身产生),我试图确定 FIRST 集。
我的理由是:
- 由于没有空产生式,因此只需查看每条规则右侧的第一个符号即可。
- 对于所有规则
X → tα
(作为 ta 终端和 α 任意符号串),t 在 FIRST(X) 中。 - 对于所有规则
X → Yα
(Y 是非终结符,α 是任意符号串),FIRST(Y) 的所有元素都在 FIRST(X) 中。
与 的情况一样X → Yα
,我需要 FIRST(Y) 来确定 FIRST(X),我想出了这种递归方法:
class Rule:
nextId = 0
def __init__ (self, left, right):
self.left = left
self.right = right
self.id = Rule.nextId
Rule.nextId += 1
def __repr__ (self):
return 'R{}: {} → {}'.format (self.id, self.left, ' '.join (self.right) )
class Grammar:
def __init__ (self, rules):
self.rules = {rule.id: rule for rule in rules}
self.symbols = set (symbol for rule in rules for symbol in [rule.left] + rule.right)
self.nonTerminals = set (rule.left for rule in rules)
self.terminals = self.symbols - self.nonTerminals
self.calculateFirst ()
def calculateFirst (self):
self.first = {}
for nonTerminal in self.nonTerminals:
self.first [nonTerminal] = self.getFirst (nonTerminal)
def getFirst (self, symbol):
if symbol in self.first: return self.first [symbol]
first = set ()
for rule in (rule for rule in self.rules.values () if rule.left == symbol):
prefix = rule.right [0]
if prefix == symbol: continue
if prefix in self.terminals: first.add (prefix)
else: first |= self.getFirst (prefix)
return first
#here be dragons
rules = [Rule ('S', ['E'] ), Rule ('E', ['T'] ), Rule ('E', ['(', 'E', ')'] ), Rule ('T', ['n'] ), Rule ('T', ['+', 'n'] ), Rule ('T', ['T', '+', 'n'] ) ]
g = Grammar (rules)
print ('Rules:')
for rule in g.rules.values (): print ('\t{}'.format (rule) )
for nonTerminal in g.nonTerminals:
print ('First ({}) = {}'.format (nonTerminal, g.first [nonTerminal] ) )
对于维基百科上给出的语法,这会产生以下结果:
Rules:
R0: S → E
R1: E → T
R2: E → ( E )
R3: T → n
R4: T → + n
R5: T → T + n
First (S) = {'+', '(', 'n'}
First (E) = {'+', '(', 'n'}
First (T) = {'+', 'n'}
对于另一种语法,它产生:
Rules:
R0: S → N
R1: N → V = E
R2: N → E
R3: E → V
R4: V → x
R5: V → * E
First (V) = {'*', 'x'}
First (S) = {'*', 'x'}
First (N) = {'*', 'x'}
First (E) = {'*', 'x'}
我的问题是:
1. 对于符合 I 和 II 的任何给定规则集,该算法是否会停止。
2. 对于符合 I 和 II 的任何给定规则集,该算法是否真的产生所有非终结符的正确 FIRST 集。
3. 有什么聪明的方法可以做到这一点吗?
我提前感谢您的评论和回答。
注意事项:我不确定是在此处发布还是在代码审查中发布,但由于我不知道我的代码是否有效(即产生预期结果),我决定将其发布在这里。如果您觉得它属于 CR,请告诉我。