単純優先順位文法

Context-free formal grammar

コンピュータサイエンスにおいて、単純優先順位文法は、単純優先順位パーサで解析できる文脈自由 形式文法です。^[1] この概念は1964年にクロード・ペアによって初めて考案され、^[2]その後、ロバート・フロイドのアイデアから、ニクラウス・ヴィルトとヘルムート・ウェーバーによって再発見されました。彼らは1966年にCommunications of the ACMに「EULER：ALGOLの一般化とその形式的定義」と題された論文を発表しました。^[3]

形式的定義

P内のすべての生成規則が以下の制約に従う 場合、 G = ( N、Σ、P、S ) は単純優先順位文法です。

• 消去規則（ε生成規則）はありません。
• 無駄な規則（到達不可能な記号や非生産的な規則）はありません
• 記号X、Y ( X、Y ( N ∪ Σ) )の各ペアに対して、ヴィルト・ウェーバーの優先順位関係は1つだけ存在します。 ${\displaystyle \in }$
• G は一意に可逆です。

例

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

優先順位表

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

単純優先順位パーサー

単純優先順位パーサは、文脈自由文法用のボトムアップパーサの一種で、単純優先順位文法でのみ使用できます。

パーサの実装は、汎用ボトムアップパーサと非常によく似ています。スタックは、右端の導出から文形式の有効な接頭辞を格納するために使用されます。記号 ⋖、≐、および ⋗ は、ピボットを識別し、いつシフトするか、いつリダクションするかを判断するために使用されます。

実装

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

SearchProductionToReduce(スタック)

• スタックの最上位の⋖を見つける。これとそれより上のすべての記号がピボットである。
• ピボットを右側に持つ文法の生成規則を見つける。

例

乗算と加算の演算を含む算術式を解析できる次の言語があるとする。

E --> E + T' | T'T' --> TT --> T * F | FF --> ( E' ) | numE' --> E

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

解析表：

	E	E'	T	T'	F	+	*	（	）	num	$
E						≐			⋗
E'									≐
T						⋗	≐		⋗		⋗
T'						⋗			⋗		⋗
F						⋗	⋗		⋗		⋗
+			⋖	≐	⋖			⋖		⋖
*					≐			⋖		⋖
(	⋖	≐	⋖	⋖	⋖			⋖		⋖
)						⋗	⋗		⋗		⋗
num						⋗	⋗		⋗		⋗
$	⋖		⋖	⋖	⋖			⋖		⋖

スタック	優先順位	入力	アクション
$	⋖	2 * (1 + 3)$	シフト
$ ⋖ 2	⋗	* (1 + 3)$	REDUCE (F -> num)
$ ⋖ F	⋗	* (1 + 3)$	REDUCE (T -> F)
$ ⋖ T	≐	* (1 + 3)$	シフト
$ ⋖ T ≐ *	⋖	(1 + 3)$	シフト
$ ⋖ T ≐ * ⋖ (	⋖	1 + 3 )$	シフト
$ ⋖ T ≐ * ⋖ ( ⋖ 1	⋗	+ 3 )$	4× (F -> num) (T -> F) (T' -> T) (E -> T ') を減算する
$ ⋖ T ≐ * ⋖ ( ⋖ E	≐	+ 3 )$	シフト
$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ +	⋖	3 )$	シフト
$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3	⋗	)$	3× 減算 (F -> num) (T -> F) (T' -> T)
$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T	⋗	)$	2× 減算 (E -> E + T) (E' -> E)
$ ⋖ T ≐ * ⋖ ( ≐ E'	≐	)$	シフト
$ ⋖ T ≐ * ⋖ ( ≐ E' ≐ )	⋗	$	減算 (F -> ( E' ))
$ ⋖ T ≐ * ≐ F	⋗	$	減算 (T -> T * F)
$ ⋖ T	⋗	$	2×減算 (T' -> T) (E -> T')
$ ⋖ E		$	承認

ヴィルト-ウェーバーの先行関係

コンピュータサイエンスにおいて、形式文法が単純優先文法であるかどうかを判断するには、記号のペア間のヴィルト＝ウェーバー関係が必要です。このような場合、単純優先パーサーを使用できます。この関係は、コンピュータ科学者のニクラウス・ヴィルトとヘルムート・ウェーバーにちなんで名付けられました。 ${\displaystyle (V_{t}\cup V_{n})}$

目標は、実行可能な接頭辞がピボットを持ち、縮小する必要がある時期を特定することです。Aはピボットが見つかったことを意味し、Aは潜在的なピボットが始まっていることを意味し、Aは同じピボットに関係が残っていることを意味します。 ${\displaystyle \gtrdot }$ ${\displaystyle \lessdot }$ ${\displaystyle \doteq }$

形式的定義

${\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}}}$

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

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

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

• RelationTable := ∅
• 各生成規則について ${\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, ) ここで、Sは文法の最初の非終端記号、$は限界マーカーです ${\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}$
• add(RelationTable, ) ここで、Sは文法の最初の非終端記号、$は限界マーカーです ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}$

${\displaystyle \lessdot }$およびは、定義されたとおりに要素ではなく集合で使用されるため、この場合、集合／要素間のすべての直積を加算する必要があります。 ${\displaystyle \gtrdot }$

例1

${\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}$
  • a 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}}}$

例2

${\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}$

• • a 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}}}$

注釈

1. 『構文解析、翻訳、コンパイルの理論：コンパイル』、アルフレッド・V・エイホ、ジェフリー・D・ウルマン、プレンティス・ホール、1972年
2. Claude Pair (1964). "Arbres, piles et compilation". Revue française de traitement de l'information .、英語：木、スタック、そしてコンパイル
3. Machines, Languages, and Computation、Prentice–Hall、1978年、ISBN 9780135422588 WirthとWeber [1966]はFloydの優先順位文法を一般化し、単純な優先順位文法を得た。

参考文献

• Alfred V. Aho、Jeffrey D. Ullman (1977). Principles of Compiler Design . 第1版、Addison–Wesley
• William A. Barrett、John D. Couch (1979)。『コンパイラ構築：理論と実践』。Science Research Associate。
• Jean-Paul Tremblay、PG Sorenson (1985)。『コンパイラ記述の理論と実践』。McGraw–Hill。

参考文献

• Aho、Alfred V.、Ullman、Jeffrey D.、『構文解析、翻訳、コンパイルの理論』

外部リンク

• クレムソン大学の「単純優先順位関係」

Retrieved from "https://en.wikipedia.org/w/index.php?title=Simple_precedence_grammar&oldid=1316999801#Simple_precedence_parser"