第4章 構文解析 4.1 4.2 4.3 4.4 4.5 4.6 下降型解析と上昇型解析 再帰下降解析 LL解析 LR解析 構文解析の自動化 演算子優先順位解析 4.1 下降型解析と上昇型解析 (1)構文解析とは ■構文解析(Syntax AnalysisまたはParsing) 1つの文法の下で終端記号からなる列の導出木を 再構成すること。(導出の逆) ■解析木(得られる結果、Parse Tree) ■語彙解析は解析の対象が文字だったが、 構文解析の対象は記号 (2)構文木例 ■BNF E ::= T ::= F ::= I ::= E T E+T T*F (E) a | | | | b T F I | c T F I F E ■入力記号列 a*(b+c) a * ( E T F I b T F I + c ) (3)下降型解析と上昇型解析 ■下降型解析(Top Down Parsing) または下向き構文解析 構文木を根(文法の出発記号)から葉(解析しよう とする字句)の方に作っていく ■上昇型解析(Bottom Up Parsing) または上向き構文解析 構文木を葉から根の方に作っていく (4)構文解析の進行 • 下降型構文解析 • 上昇型構文解析 未決定 未決定 決定済み 入力 記号列 入力 記号列 読込み 読込み 未決定 (5)下降型構文解析 決定済み 入力 記号列 読込み 【BNF】 識別子リスト::=識別子|識別子, 識別子リスト 識別子::=a | b | c 【入力記号列】 a, b, b 等価なProlog 識別子リスト(L):-識別子(L). 識別子リスト([A|[C|L]]) :-識別子(A),コンマ(C) ,識別子リスト(L). コンマ(‘,’). 識別子(‘a’). 識別子(‘b’). 識別子(‘c’). ?識別子リスト(“a,b,b”). 識別子リスト →識別子, 識別子リスト →a, 識別子リスト →a, 識別子, 識別子リスト →a, b, 識別子リスト →a, b, 識別子 →a, b, b 未決定 入力 記号列 読込み (6)上昇型構文解析 【BNF】 識別子リスト::=識別子|識別子リスト, 識別子 識別子::=a | b | c 下降型と逆である 【入力記号列】 ことに注意 a, b, b a,b,b →識別子,b,b →識別子リスト,b,b →識別子リスト,識別子,b →識別子リスト,b →識別子リスト,識別子 →識別子 (7)演算子順序解析 演算子順序解析(Operator Precedence Analysis) 【誤った 例】 A + B * 【正しい例】 C A + B * C ①入力記号列に構文エラーがあるときの処理が難しい。 ②適用できる文法の範囲が狭い。 一般にこう言われる が私の意見は異なる 式の部分だけに使用されることが多い
© Copyright 2025 ExpyDoc