パーサの例

ウィキペディア小見出し辞書

パーサの例

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/03 01:09 UTC 版)

「再帰下降構文解析」の記事における「パーサの例」の解説

以下の文法はLL(1)形式のEBNFの例である（ニクラウス・ヴィルトのPL/0言語）。単純化のため、ident と number は終端記号とされている: program = block "." . block = ["const" ident "=" number {"," ident "=" number} ";"] ["var" ident {"," ident} ";"] {"procedure" ident ";" block ";"} statement . statement = [ident ":=" expression | "call" ident | "begin" statement {";" statement} "end" | "if" condition "then" statement | "while" condition "do" statement ] . condition = "odd" expression | expression ("="|"#"|"<"|"<="|">"|">=") expression . expression = ["+"|"-"] term {("+"|"-") term} . term = factor {("*"|"/") factor} . factor = ident | number | "(" expression ")" . 終端記号は引用符で囲まれている（identとnumber以外）。各非終端記号は文法規則で定義されている。 以下に示す予言的パーサが上記文法を正確に反映している点に注意されたい。各非終端記号に対応したプロシージャが存在している。構文解析はトップダウン的に行われ、全非終端記号が処理されるまで行われる。入力コード（プログラムの部分）の先頭の単語は大域変数 sym に格納されている。そして大域関数 getsym を使うことで sym を更新する。 typedef enum {ident, number, lparen, rparen, times, slash, plus, minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon, endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma, varsym, procsym, period, oddsym} Symbol;Symbol sym;void getsym(void);void error(const char msg[]);void expression(void);int accept(Symbol s) { if (sym == s) { getsym(); return 1; } return 0;}int expect(Symbol s) { if (accept(s)) return 1; error("expect: unexpected symbol"); return 0;}void factor(void) { if (accept(ident)) { ; } else if (accept(number)) { ; } else if (accept(lparen)) { expression(); expect(rparen); } else { error("factor: syntax error"); getsym(); }}void term(void) { factor(); while (sym == times || sym == slash) { getsym(); factor(); }}void expression(void) { if (sym == plus || sym == minus) getsym(); term(); while (sym == plus || sym == minus) { getsym(); term(); }}void condition(void) { if (accept(oddsym)) { expression(); } else { expression(); if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) { getsym(); expression(); } else { error("condition: invalid operator"); getsym(); } }}void statement(void) { if (accept(ident)) { expect(becomes); expression(); } else if (accept(callsym)) { expect(ident); } else if (accept(beginsym)) { do { statement(); } while (accept(semicolon)); expect(endsym); } else if (accept(ifsym)) { condition(); expect(thensym); statement(); } else if (accept(whilesym)) { condition(); expect(dosym); statement(); }}void block(void) { if (accept(constsym)) { do { expect(ident); expect(eql); expect(number); } while (accept(comma)); expect(semicolon); } if (accept(varsym)) { do { expect(ident); } while (accept(comma)); expect(semicolon); } while (accept(procsym)) { expect(ident); expect(semicolon); block(); expect(semicolon); } statement();}void program(void) { getsym(); block(); expect(period);}