generated at
解析木
from 構文解析

parse tree
構文木、構文解析木
構文規則をどう適用すればよいかを表すもの
構文を正確に表すが演算の意味を示すには冗長
葉に括弧を含む
根は開始記号、節は非終端記号、葉は終端記号か\epsilon


解析木の表現
プリオーダー系列
インオーダー系列
ポストオーダー系列


生成器規則から解析木を書く自分なりの手順
具体的な文から一つずつ還元していく
このときに、どこを還元したかを丸などをつけてメモっておくといい
そのあとに、↑の一番下を根にして葉を生やしていく

具体例
以下のような生成器規則が与えられたとする
BNF
F -> F ∨ T | T T -> T ∧ L | L L -> ¬L | (L) | i
問題 i ∨ i ∧ ¬ i の解析木を書け
手順1: 一つずつ還元していく
還元した箇所をメモがてら角括弧で囲うことにする
還元
i ∨ i ∧ ¬i -> [L] ∨ [L] ∧ ¬[L] -> L ∨ L ∧ [L] -> L ∨ [T] ∧ L -> L ∨ [T] -> [T] ∨ T -> [F] ∨ T -> [F]
手順2: これの最下部のFを根にして一手順ずつ遡っていき葉を生やしていく
解析木
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