2023/02/23
LL(k) と LR(k) の違いが分かった
やったこと
- 服を買った
- タイガーブック 3 章の続きを読んだ
タイガーブックの構文解析の章の続きを読んだ。
昨日は LL(1)文法だったが、今日は LR(1)文法と LR(0)文法、SLR 文法の部分を読んだ。
LR 文法の構文解析表の作成アルゴリズムが疑似コードで書かれていて、それの理解に時間がかかった。
構文解析表を作って有限オートマトンでスタックの挙動を決定しなければいけないため、たしかに自作するのは手間がかかりそうだと実感した。
時間に余裕があるときに、小さな文法の LR 構文解析器を作ってみたい。
また LL(1) 文法の構文解析器を写経していたため、 LL 文法と LR 文法の違いが分かりやすくて良かった。
LL(1) も LR(1) も 1 つ先読みするが、上向きに解析するか下向きに解析するかの違いが重要だと分かった。
例えば以下の文法があったとする。
X → aa
Y → aabLL(1) 文法では a を読んだ時点でそれが X か Y かを判断しなければいけないため、これは受理できない (左括り出しで受理できる文法にできる) が、 LR(1) 文法では aa を読んでから入力を 1 つ先読みして $ なら X, b なら Y に還元できるため受理できる。
文脈自由言語の種類について書かれた参考になる記事を見つけたのでメモしておく。
https://lpha-z.hatenablog.com/entry/2019/01/13/231500
思ったこと
田原さん (ジャーナリストの田原総一郎) が朝食を食べる動画が最近好き。 彼の政治的な主張や功績はよく知らないが、人が朝食をとっている動画はその人の生活が滲み出ていてあたたかさというか人間味を感じられるから良い。
https://www.youtube.com/watch?v=vDZZzMmprzw
今日の英会話
日本がウクライナに 7390 億円の支援を決定した話。