文脈自由言語の階層について

去年もこんな話を書いた気がします。

文脈自由言語の階層についての情報ってネット上ではまとまった形ではあまり手に入らないような気がします。調べたことをまとめておきます。

文脈自由文法と文脈自由言語の違い

文脈自由文法と文脈自由言語という、二つの混同しやすい用語があります。

まず、「言語」とは(有限)文字列の(無限かもしれない)集合のことです。○○言語というのは、特定の特徴を持つ言語の集合(言語クラス)のことです。 文脈自由言語とは、与えられた文字列がその集合に属しているかの判定(メンバーシップ問題)がプッシュダウンオートマトンを用いると解けるような言語です。その集合は普通は無限集合ですが、有限集合であっても問題ありません。ただし、有限集合であれば自明に正規文法で記述できる正規言語になるため、わざわざ文脈自由言語という必要がありません(有限集合なので/foo|bar|baz/のようにすべての要素を枚挙することが可能です)。 正規言語のメンバーシップ問題は有限状態オートマトンで解かれますが、非決定性があってもなくてもどちらでも同じになります。一方、文脈自由言語のメンバーシップ問題を解くためのプッシュダウンオートマトンには、これとは違い非決定性が必要です。なお、非決定性が必要とはいっても、文脈自由言語のメンバーシップ問題は全探索的考え方で多項式時間で解くことができます。

一方、「文法」とはそのような集合を記述する方法のことです。一般にある集合を記述する方法は複数ありえるので、「言語」と「文法」の違いは重要になります。 集合の元が無限にある場合、その集合を記述するには一工夫必要です。実際の記述には、BNF記法や正規表現など、読みやすい形がいくつか提案されています。なお、いわゆる正規表現は、正規言語を超えた記述能力を持つような拡張が加えられていることがあるので注意が必要です(たとえば後方参照は、文脈自由言語すら超えた表現力を持ちます)。

LL(0)

前から読んでいき、先読みをせずに次の構造が何であるかを予言する必要があるため、LL(0)文法で記述できる集合は、単元集合のみです。

また、LL(0)言語も同様に単元集合だけであり、正規言語に真に包含されます。

LL(1)

前から読んでいき、一トークンの先読みだけにより、どの生成規則を適用するかを決めることができるような文法をLL(1)文法と言います。

また、そのような文法で記述することができる言語をLL(1)言語と言います。つまり、「頑張ればLL(1)文法であるような文法が作れる」ような言語です。LL(1)言語だからと言って、文法を適当に作った場合にはLL(1)文法である保証はないということです。また、現実的な問題として、その文法の生成する構文木が作りたい構文木と一致している保証はありません。実際、a+b*cのような「数式」はうまく作ったLL(1)文法で解析できるにはできるのですが、変な構文木になってしまいます。

正規言語はLL(1)言語の真部分集合になります。

正規言語ではなく、文脈自由言語であるような集合として有名な  \lbrace a^ n b^ n | n > 0\rbrace はLL(1)言語です。その他、「対応の取れた括弧」などもLL(1)言語です。

LR(0)

前から読んでいき、先読みなしにこのトークンがどの生成規則から生成されたものかを決めることができるような文法をLR(0)文法と言います。 先読みがないとはいえ、生成規則が生成するトークンすべてがあっていることを確かめてから構文木を作成するため、ある程度強力です。 しかし、正規言語の一部は受理できないなど、偏った性能を持ちます。

具体的には、xを一文字以上の文字列、w,yを空でもよい文字列としたとき、wとwxとyが言語に含まれているならば、yxも言語に含まれている、という性質を持った言語のみ受理可能です(参考文献[1]"On LR(k) Grammars and Languages"の定理3.1)。

LL(1)だがLR(0)ではない言語

LL(1)言語であってもLR(0)言語ではない言語は、先読みが本質的に重要な言語です。  \lbrace ab^ n | n > 0\rbrace \cup \lbrace cd^ n | n > 0\rbrace がそれに当たります。ここで、b(d)の後にb(d)が続くのかが先読みの必要な情報であり、a(c)を読んだ、という情報を手放さずに先読みを行えるかという点が重要になります。一方、  \lbrace ab^ n | n > 0\rbrace を解析するためにはaを読んだという情報は不要なため、LR(0)でも解析できます。参考文献[1]によれば、aもabもcもこの言語に入っているのにcbはこの言語に入っていないのでLR(0)では解析できないと書かれていました。

LR(0)だがLL(k)ではない言語

LL(k)言語ではない、というのはどんなに大きな有限のkを持ってきてもLL(k)文法では記述できない、という言語です。  \lbrace a^ nb^ n | n > 0 \rbrace \cup \lbrace a^ nc^ n | n > 0 \rbrace がそれに当たります。aを見た時点では、それがbに対応するものかcに対応するものかわからないため、二つあるであろう生成規則のどちらを選ぶべきかわかりません。また、aが続く数は無制限であるため、kトークン先読みではこの問題を解決することができません。

LL(2)

LL(1)との違いは先読みトークン数の増加だけですが、LL(1)を厳密に包含するクラスであり、LL(1)よりも高い記述力を持った言語クラスです。

一般に、LL(k+1)言語はLL(k)言語を厳密に包含するクラスです(参考文献[2]"Properties of Deterministic Top Down Grammars")。

LL(2)でないと記述できない言語の例はなかなか見ませんが、この論文には具体例が上がっています。具体的には、  \lbrace a^ n (b^ kd | b | cc)^ n | n > 0\rbrace という言語はLL(k+1)では記述できるものの、LL(k)では記述できない、というものだそうです。まず、  (b^ kd | b | cc) の先頭にはdが現れることがありません。そこで、k+1トークン先読みしてdが出現するかを確認することにより、 bk dを生成する規則を選ぶべきなのかbを生成する規則を選ぶべきなのかの判別が可能です。逆に直観的にわかるように、kトークンの先読みなしではそのどちらの規則を選ぶべきか判断がつきません(論文には形式的な証明が書いてありました)。ccが存在するのは、  b^ {k-1}d を自由な位置に挿入することができるような文法として書けてしまうことを防止するためだと思われます。

SLR法

Simple LR(1)法というアルゴリズムのことであり、SLR法と言ったらこれのことを指します。また、このアルゴリズムで解析可能な文法をSLR文法と呼びます。

LR(0)法により解析を行おうとして問題が発生するのは以下のパターンです。

  • 複数の異なる生成規則の右辺が完成した状況(reduce-reduce conflict)。どの生成規則だったと言うべきかわからない。
  • 生成規則の右辺が完成した状況だが、もっと長い生成規則の途中という可能性もある状況(shift-reduce conflict)。前者であればその生成規則だと言うべきタイミングは今しかないが、スルーすべきなのかもしれない。

こういう場合、次のトークンを先読みすることにより問題を解決できる可能性があります。各非終端記号の後に来うるトークンの集合(Follow-set)を事前に計算しておきます。先読みトークンの情報をこれに照らし合わせて判断するのがSLR法です。

SLR法は、LR(0)文法を全て解析することができます(真に包含します)。

LALR(1)法

LookAhead LR(1)法というアルゴリズムの名前であり、これを用いて解析可能な文法をLALR(1)文法と呼びます。

SLRでは単にその非終端記号の後に来うるトークンの集合を用いただけでした。ここにいたるまでの情報を利用し、直後に来うるトークンの集合をさらに選別したもの(Lookahead-set)を使うのがLALR(1)法です。

SLR法で解析できないがLALR(1)法で解析できる文法は、以下のような感じです。

(1) S→V=E
(2) S→E
(3) E→V
(4) V→p
(5) V→q
(6) V→*E

これが生成する言語に含まれる文字列は、**p = ***qのようなポインタ同士の代入文です。

この文法では、Vの後には=が来る可能性があります。しかしその情報を使っても、=を先読みした時に(3)の生成規則を使ってVをEに還元するべきか、それとも(1)の生成規則の途中なのでスルーすべきなのか、判断がつきません。これがSLR法で解析できない理由です。

一方、LALR(1)法では解析可能です。なぜなら、Eから生まれたVであれば後ろには文字列終端が来るはずなのでそれを先読みしたらEに還元すべきであり、Sから生まれたVであれば後ろには=が来るはずなのでそれを先読みしたらスルーすべき、とそこに至るまでの情報を活用して解析が可能だからです。

LALR(1)法は、SLR文法を全て解析できます(真に包含します)。

LR(1)法

これもアルゴリズムの名前であり、これを用いて解析可能な文法をLR(1)文法と呼びます。

LALR(1)法では、先読みトークンだけが異なる状態を同一視することで状態数を減らすということを行っています。 これを行わないのがLR(1)法です。

この違いによりLR(1)法では解析できるのにLALR(1)法では解析できない文法は、以下のようなものです。

S→[A]
S→[B)
S→(B]
S→(A)
A→a
B→a

LR(1)法は、LALR(1)文法を全て解析できます(真に包含します)。

LR(2)法、LR(k)法

先読みトークン数を増やしたLR法です。まずつかわれることがないので割愛します。LR(2)法はLR(1)文法を全て解析できるうえ、LR(1)法では解析できずLR(2)法を用いないと解析できないという文法も存在します(真に包含します)。 また、LL(k)文法はLR(k)法で解析することができます(真に包含します)。

決定性文脈自由言語

実は、SLR法、LALR(1)法、LR(1)法、LR(2)法、……LR(k)法で解析できる言語は、決定性文脈自由言語という言語クラスと一致することが知られています。

これは、SLR法<LALR(1)法<LR(1)法<LR(2)法<……という文脈自由文法の解析法の階層は、文脈自由言語には存在しないということです。つまり、うまく文法を記述しさえすれば、どんな決定性文脈自由文法でもSLR文法で書けるということです。

また、LL(k)言語やLR(0)言語は決定性文脈自由言語の真部分集合です。

あいまいでない文脈自由言語

「回文」や  \lbrace a^ nb^ n | n > 0\rbrace \cup \lbrace a^ nb^ {2n} | n > 0\rbrace などは、解析に非決定性が必要な言語です。これらはLL法やLR法では解析できず、全探索的考え方で動作するGLR法などで解析されます。

本質的にあいまいな文脈自由言語

言語に含まれる文字列について、複数の導出が可能になってしまうような文法をあいまいな文法と呼びます。たとえば、以下のような文法はあいまいな文法です。

S→S+S
S→x

たとえば、x+x+xの導出は二通りあります。右結合か左結合かを明示した文法とすればあいまいでない文法として記述できます。

しかし、どのように文法を記述しても文法があいまいな文法になってしまう言語もあります。それは本質的にあいまいな言語と呼ばれます。

 \lbrace a^ nb^ nc^ md^ m | n, m > 0\rbrace \cup \lbrace a^ nb^ mc^ md^ n | n, m > 0\rbrace

たとえば上に上げた言語は本質的にあいまいな言語です。 二つの集合の共通部分である  \lbrace a^ nb^ nc^ nd^ n | n > 0\rbrace は文脈自由言語ではないものの典型例になっています。 つまり、その部分に特殊化された文法を書けないため、二つの集合に対応した構文木のどちらとしても解析される(=あいまい)、という直観的な解釈が可能です。 Wikipediaには、とある本に証明が載っていると書いてありますがその証明は形式的なものではありませんでした。

文脈自由文法にまつわる決定不可能な問題

  • ある文脈自由文法が「全文字列」という言語を記述しているか否か(チューリングマシンの停止性問題を帰着できる)。
  • ある文脈自由文法が別のある文脈自由文法と同じ言語を記述しているか否か(先の問題を含むので当然決定不可能)。
  • ある文脈自由文法の記述する言語は、別のある文脈自由文法の記述する言語に包含されるか否か( A \subseteq B \wedge B \subseteq A の判定は先の問題と等価であるため)。
  • ある文脈自由文法が記述する言語と別の文脈自由文法が記述する言語の両方に含まれる文字列はあるか否か。
  • ある文脈自由文法があいまいか否か。
  • ある文脈依存文法が実は文脈自由言語を表しているか否か。

決定不可能な問題に対するよくある誤解として「この形式をしている問題は決定不可能」というものがありますが、「この形式をしている問題を 全て 解ける(統一的な)アルゴリズムはない」という意味であり、個々の問題インスタンスは決定可能です。たとえば、特定の文脈自由文法があいまいか否か、などは頑張れば証明が可能です。

参考文献

[1] M. M. Geller, M. A. Harrison, Theoretical Computer Science, 1977, 4, 245-276.

[2] D.J. Rosenkrantz, R.E. Stearns, Inf. Control, 1970, 17, 226-256.