解析木
from 構文解析
parse tree
構文木、構文解析木
構文規則をどう適用すればよいかを表すもの
構文を正確に表すが演算の意味を示すには冗長
葉に括弧を含む
根は開始記号、節は非終端記号、葉は終端記号か$ \epsilon
解析木の表現
プリオーダー系列
インオーダー系列
ポストオーダー系列
生成器規則から解析木を書く自分なりの手順
具体的な文から一つずつ還元していく
このときに、どこを還元したかを丸などをつけてメモっておくといい
そのあとに、↑の一番下を根にして葉を生やしていく
具体例
以下のような生成器規則が与えられたとする
code:BNF
F -> F ∨ T | T
T -> T ∧ L | L
L -> ¬L | (L) | i
問題i ∨ i ∧ ¬ iの解析木を書け
手順1: 一つずつ還元していく
還元した箇所をメモがてら角括弧で囲うことにする
code:還元
i ∨ i ∧ ¬i
-> L ∨ L ∧ ¬L
-> L ∨ L ∧ L
-> L ∨ T ∧ L
-> L ∨ T
-> T ∨ T
-> F ∨ T
-> F
手順2: これの最下部のFを根にして一手順ずつ遡っていき葉を生やしていく
code:解析木
F
F -> F
-> T
F -> F -> T
-> T
F -> F -> T -> L
-> T
F -> F -> T -> L
-> T -> T
-> L
F -> F -> T -> L
-> T -> T -> L
-> L
F -> F -> T -> L
-> T -> T -> L
-> L -> ¬L
F -> F -> T -> L -> i
-> T -> T -> L -> i
-> L -> ¬L -> i