2

LR パーサーの場合、FIRST セットは次のように定義されます ( source )。

FIRST(A) は、非終端記号 A に一致するルールの連鎖の最初の要素として現れる端子のセットです。

(I) 空の生成を許可しない (つまり、 format の規則がないX → ε) および (II) 適切である (つまり、シンボル自体を生成しない) CFG が与えられたので、FIRST セットを決定しようとしています。

私の理由は次のとおりです。

  • 空のプロダクションがないので、各ルールの右側の最初のシンボルを見るだけで十分です。
  • すべての規則X → tα(ta 端子と α は任意の記号列) について、t は FIRST(X) にあります。
  • すべての規則X → Yα(Y は非終端記号、α は任意の記号列) について、FIRST(Y) のすべての要素は FIRST(X) にあります。

の場合と同様に、X → YαFIRST(X) を決定するには FIRST(Y) が必要です。この再帰的なアプローチを思い付きました。

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. これを行う賢い方法はありますか?

コメントと回答に事前に感謝します。

Nota bene : これをここに投稿するか、コード レビューに投稿するかはわかりませんでしたが、コードが機能するかどうか (つまり、期待される結果が得られるかどうか) がわからないため、ここに投稿することにしました。むしろ CR に属していると思われる場合は、お知らせください。

4

1 に答える 1

2

null 可能な非端末がない場合、プログラムは終了して正しい答えを生成するという意味で、プログラムは機能すると思います。(自己参照の非端末は問題ないはずです。)

巧妙な方法があります。いつもあるんじゃない？よくあることですが、賢い解決策はRobert Tarjanによって考え出されましたが、他の賢い解決策もあります。ただし、ほとんどの文法では、通常、単純なソリューションを使用するのと同じくらい高速です。

は非終端記号であり、任意の記号A directly-starts-with VでAある関係を定義します。多少の生産がある場合。null 許容の非終端記号を持たない文法の場合、単純に関係の推移閉包であり、範囲は終端記号に制限されます。Tarjan のアルゴリズム (グラフの強連結成分を計算する) は、この問題に対する高速で洗練されたソリューションをもたらします。VA directly-starts-with VA → V αFIRST(A)directly-starts-with

推移閉包を計算するための優れたアルゴリズムは他にもあります。Floyd-Warshallも人気のある選択肢です。FW を見て推測できるように、推移閉包を行列の乗算に非常に似たものに減らすことができます。行列乗算の時間の複雑さを軽減するために使用できる同じ手法が、推移閉包にも適用されます。ただし、現実の世界では特に役に立ちません。

null 許容の非端末は、それらを識別できる限り、状況をそれほど複雑にしません (これは非常に簡単です)。directly-starts-withnull 許容の非終端記号のみが前にある RHS に任意の記号を含めるように拡張するだけです。null 許容の非終端記号を識別するための通常のアルゴリズムでは、directly-starts-withほとんど無料で提供されます。

于 2013-09-18T05:37:22.623 に答える