単純な優先順位文法

• 開始記号Sを持つ文法のWirth–Weber優先順位関係表を計算します。
• 開始マーカー$でスタックを初期化します。
• 解析対象の文字列（入力）に終了マーカー$を追加します。
• スタックが「$ S」になり、入力が「$」になるまで
  • テーブル内で Top(stack) と NextToken(Input) の関係を検索します。
  • 関係が⋖または≐の場合
    • シフト：
    • プッシュ(スタック、関係性)
    • Push(Stack, NextToken(Input))
    • RemoveNextToken(Input)
  • 関係が⋗である場合
    • 減らす：
    • SearchProductionToReduce(Stack)
    • スタックからピボットを削除する
    • 生成規則の非終端記号とスタックの最初の記号（上から順に）との関係を表から検索します。
    • プッシュ(スタック、関係性)
    • プッシュ（スタック、非終端）

SearchProductionToReduce (Stack)

• スタックの一番上の⋖を見つけます。これとそれより上のすべてのシンボルがピボットです。
• ピボットを右辺とする文法の生成規則を求めなさい。

乗算と加算演算を含む算術式を解析できる以下の言語を仮定します。

E --> E + T' | T' T' --> T T --> T * F | F F --> ( E' ) | num E' --> E 

numは終端記号であり、字句解析器は任意の整数をnumとして解析します。Eは算術式を表し、Tは項、Fは因数です。

そして解析テーブル：

${\displaystyle G=\langle V_{n},V_{t},S,P\rangle }$

${\displaystyle {\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\beta \in P\\A\in V_{n}\\\alpha ,\beta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\lessdot Y&\iff {\begin{cases}A\to \alpha XB\beta \in P\\B\Rightarrow ^{+}Y\gamma \\A,B\in V_{n}\\\alpha ,\beta ,\gamma \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\gtrdot Y&\iff {\begin{cases}A\to \alpha BY\beta \in P\\B\Rightarrow ^{+}\gamma X\\Y\Rightarrow ^{*}a\delta \\A,B\in V_{n}\\\alpha ,\beta ,\gamma ,\delta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\\a\in V_{t}\end{cases}}\end{aligned}}}$

記号に対して3つの集合を定義します。

${\displaystyle {\begin{aligned}\mathrm {Head} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}Y\alpha \}\\\mathrm {Tail} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}\alpha Y\}\\\mathrm {Head} ^{*}(X)&=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}\end{aligned}}}$

Head ^* ( X ) は、 Xが終端記号の場合はX そのもので、Xが非終端記号の場合は、Head ^* ( X ) は Head ⁺ ( X )に属する終端記号のみからなる集合です。この集合は、 LL パーサーで説明されているFirst-setまたはFi( X )と同等です。

Head ⁺ ( X ) と Tail ⁺ ( X ) は、 Xが終端記号の場合、 ∅になります。

関係を計算するための擬似コードは次のとおりです。

• リレーションテーブル := ∅
• 各作品について${\displaystyle A\to \alpha \in P}$
  • α内の隣接する 2 つのシンボルXYそれぞれについて
    • add(RelationTable,${\displaystyle X\doteq Y}$）
    • add(RelationTable,${\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}$）
    • add(RelationTable,${\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}$）
• add(RelationTable,${\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}$ここで、Sは文法の最初の非終端記号であり、$は制限マーカーである。
• add(RelationTable,${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}$ここで、Sは文法の最初の非終端記号であり、$は制限マーカーである。

${\displaystyle \lessdot }$そして${\displaystyle \gtrdot }$は、定義された要素の代わりにセットとともに使用されます。この場合、セット/要素間のすべてのデカルト積を追加する必要があります。

${\displaystyle S\to aSSb|c}$

• ヘッド⁺ ( a ) = ∅
• ヘッド⁺ ( S ) = { a, c }
• ヘッド⁺ ( b ) = ∅
• ヘッド⁺ ( c ) = ∅
• テール⁺ ( a ) = ∅
• テール⁺ ( S ) = { b, c }
• テール⁺ ( b ) = ∅
• テール⁺ ( c ) = ∅
• ヘッド^* ( a ) = a
• ヘッド^* ( S ) = { a, c }
• ヘッド^* ( b ) = b
• ヘッド^* ( c ) = c
• ${\displaystyle S\to aSSb}$
  • Sの隣に
    • ${\displaystyle a\doteq S}$
    • ${\displaystyle a\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle a\lessdot a}$
      • ${\displaystyle a\lessdot c}$
  • Sの隣にSがあります
    • ${\displaystyle S\doteq S}$
    • ${\displaystyle S\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle S\lessdot a}$
      • ${\displaystyle S\lessdot c}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)}$
      • ${\displaystyle b\gtrdot a}$
      • ${\displaystyle b\gtrdot c}$
      • ${\displaystyle c\gtrdot a}$
      • ${\displaystyle c\gtrdot c}$
  • S bの隣
    • ${\displaystyle S\doteq b}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)}$
      • ${\displaystyle b\gtrdot b}$
      • ${\displaystyle c\gtrdot b}$
• ${\displaystyle S\to c}$
  • シンボルは1つしかないので、関係性は追加されません。

優先順位表

${\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}$

${\displaystyle S\to a|aT|[S]}$

${\displaystyle T\to b|bT}$

• ヘッド⁺ ( S ) = { a, [ }
• ヘッド⁺ ( a ) = ∅
• ヘッド⁺ ( T ) = { b }
• ヘッド⁺ ( [ ) = ∅
• ヘッド⁺ ( ] ) = ∅
• ヘッド⁺ ( b ) = ∅

• テール⁺ ( S ) = { a, T, ], b }
• テール⁺ ( a ) = ∅
• テール⁺ ( T ) = { b, T }
• テール⁺ ( [ ) = ∅
• テール⁺ ( ] ) = ∅
• テール⁺ ( b ) = ∅

• ヘッド^* ( S ) = { a, [ }
• ヘッド^* ( a ) = a
• ヘッド^* ( T ) = { b }
• ヘッド^* ( [ ) = [
• ヘッド^* ( ] ) = ]
• ヘッド^* ( b ) = b

• ${\displaystyle S\to aT}$

• • Tの隣に
    • ${\displaystyle a\doteq T}$
    • ${\displaystyle a\lessdot \mathrm {Head} ^{+}(T)}$
      • ${\displaystyle a\lessdot b}$

• ${\displaystyle S\to [S]}$

• • [ Sの隣に]
    • ${\displaystyle [\doteq S}$
    • ${\displaystyle [\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle [\lessdot a}$
      • ${\displaystyle [\lessdot [}$

• • S隣に]
    • ${\displaystyle S\doteq ]}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(])}$
      • ${\displaystyle a\gtrdot ]}$
      • ${\displaystyle T\gtrdot ]}$
      • ${\displaystyle ]\gtrdot ]}$
      • ${\displaystyle b\gtrdot ]}$

• ${\displaystyle T\to bT}$

• • b Tの隣に
    • ${\displaystyle b\doteq T}$
    • ${\displaystyle b\lessdot \mathrm {Head} ^{+}(T)}$
      • ${\displaystyle b\lessdot b}$

優先順位表

${\displaystyle {\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}}$