Left-toright parse, Rightmost-derivation, k-token lookahead
左から読んでいき、最右導出で解析していく
LR(k)法はk個のTokenを先読みして、「生成規則の右辺全体」に一致する入力トークンを走査し終わるまで、決定を延期する
多くのプログラミング言語はLR法で解析できる
C++とPerlは無理らしい ref
Left-toright parse, Rightmost-derivation, k-token lookahead
左から読んでいき、最右導出で解析していく
LR(k)法はk個のTokenを先読みして、「生成規則の右辺全体」に一致する入力トークンを走査し終わるまで、決定を延期する
多くのプログラミング言語はLR法で解析できる
C++とPerlは無理らしい ref
from ボトムアップ構文解析
単純LR法ともいう
閉包
closure
わかりにくいが、冷静に見ると簡単。再帰的な定義
from Parser
BNF記法っぽい記法で文法を定義できる
例
ANTLR
JavaCC
本当に何もわからない
??リンクが付いてるところについて、Twitterとかでリプを送ってもらえると泣いて喜びます
from 構文解析
parse tree
構文木、構文解析木
構文規則をどう適用すればよいかを表すもの
構文を正確に表すが演算の意味を示すには冗長
Look-Ahead, Left to Right, Rightmost derivation
先読みLR
L
left: 左から右へ処理
R
from BNF記法
reduction
導出の逆
生成規則を右辺から左辺の方向に見る
入力記号列と生成規則の右辺を照合し、一致すれば生成規則の左辺で置換する
from 導出
rightmost derivation
最も右の非終端記号が展開対象になる
#WIP
もしかしてボトムアップ構文解析かトップダウン構文解析でもまた違う?
文法規則を考えるとき
こういう入力を受理する規則を考えたい
( i1 + i2 ) * i3
トークン列を文法規則に従って構文木を構成する
プログラミング言語の構文はBNF記法を用いて記述されることが多い
構文解析を行うプログラムのことをParserと呼ぶ
分類
トップダウン構文解析
from LL法
終端記号の集合
トップダウン構文解析の解析木の非終端記号の展開時にどの生成規則を用いれば良いかを示す
DIRECTOR(A,α)は生成規則A→αの話をしている
各規則についてDIRECTORを求めればいい
ambiguous
ある文に対して2つ以上の解析木が作れるような文を「曖昧な文」と言う
逆に言えば、解析木や構文木が一意に確定する文法なら曖昧ではない
曖昧な文を一つでも持つ文法のことを曖昧な文法という
ある文法が曖昧かどうかは判定不能
top-down parser
下降型構文解析、下向き構文解析ともいう
解析木の根から葉へと導出を繰り返す
まず大きな要素から開始して徐々に細部に分解していく
根から最左導出と同じ順番で解析木を生成していく
Backus-Naur Form
バッカス・ナウア記法
文脈自由文法を記述するするためのメタ言語
プログラミングのみならず、数学的な言語理論でも用いられる
導出と簡約を用いて規則を適用させていく
redex
reducible expression
簡約可能な項
モデルを構成することをモデル化という
これは科学の多くの分野の基本的な手法
物理学で物体の運動を考える時に、剛体と重力場だけを考える感じ
ある視点において本質じゃないところは削ぎ落として定理を作っていく感じのことかなー、
プログラミングにおいても、そもそも現実世界を計算機内で扱おうなんて雑に考えれば無理そうだけど、単純なものから積み重ねていけばコードで世界を記述できるようになる
from 操作的意味論
small-step semantics
構文を小さなステップで繰り返し簡約する
簡約を繰り返した結果、これ以上簡約できない「値」になる
プログラムを実行する抽象機械には、このステップを実行する反復(iterative)機能が必要
from LR法
文法規則X -> A
を選んで、スタックから入力記号A
と状態をpopし、X
と新しい状態をスタックにpushする
A
は1個以上(?)の記号列
つまりX -> B + C
みたいなこともある
このときは、B,+,C
の3つの記号をpopし、X
に入れ替える
LR法で構文解析するのに使われる
ACTION表とGOTO表から構成される
スタックに対して決定性有限オートマトンを適用する
以下の2つより構成される
ACTION表
from LR法
先頭の入力Tokenをスタックにpushする
LR法を用いた構文解析の手順
所詮は決定性有限オートマトンなので、それを踏まえていると理解しやすい
参考
構文解析の基礎
前提
予測型構文解析とも言う
LL法のトップダウン構文解析
最初の終端記号が、どの生成規則を使用すべきか選択するための十分な情報を持っているような文法においてのみ動作する
手動で実装するのが簡単
生成器を使えるならLR法などを使ったほうが良い
context-free grammar
終端記号と非終端記号からなる
「非終端記号1つ」を「非終端記号と終端記号からなる記号列」に置き換える生成規則のみからなる文法
数を数えられたり、括弧で入れ子を表現できる点で正規表現より強力
定義