3

k > 1 に対して人為的な LR(k) 文法を作成するのは簡単です。

Input: A1 B x
Input: A2 B y                   (introduce reduce-reduce conflict for terminal a)
A1   : a
A2   : a
B    : b b b ... b              (terminal b occurs k-1 times)

しかし、LR(k > 1) で解析可能な現実世界の非 LR(1) コンピューター言語はありますか?
それとも、非 LR(1) 言語も LR(k) ではありませんか?

4

1 に答える 1

6

言語にLR(k)文法がある場合、文法LR(1)から機械的に生成できる文法がありLR(k)ます。さらに、元の構文木はLR(1)構文木から再作成できます。この定理の証明は、Parsing Theory Vol. 6.7 のセクション 6.7 に記載されています。II、Sippu & Soisalon-Soininen; 彼らはそれを、JACM 23:17-30 の MD Mickunas による「LR(k) 文法の完全なカバー問題について」(1976) に起因すると考えています。

LR(k)したがって、 として解析可能であり、 として解析可能でない言語k>1はありません。したがって、0 と 1 以外の値の言語LR(1)などは実際にはありません。LR(k) k

ただし、LR(2)文法がはるかに簡単な言語があります。yacc古典的な例の 1 つは、 の Posix 文法です;。プロダクションは識別子の後にコロンを付けて開始する必要があるため、これは明確です。そのように書くと、文法は明らかにLR(2); 上記の定理により、LR(1)文法は存在しますが、それほどきれいではありません。

于 2013-11-26T04:50:08.163 に答える