jsでbison/lex

twcritique

lex 字句解析

Lex(レック、レックス)はレキシカルアナライザ(字句解析プログラム、字句解析器)を生成するプログラムである。コンパイラの作成のためにパーサジェネレータのyaccとともに使用されることも多い

Yacc コンパイラコンパイラ

Yacc(英: yet another compiler compiler、ヤック)はパーサジェネレータの一つである。

https://docs.oracle.com/cd/E19620-01/805-5827/6j5gframh/index.html

Yacc文法

プログラム言語のパーサの書きかたは昔からしつこく研究されてきており、 かなりしっかりした定石がある。よほど変な(または曖昧な)文法でない 限り、定石にのっていけば解決できるものだ。

YACC文法ファイルは、本質的には、プログラムで処理可能な形式による、バッカス・ナウアー記法(Backus-Naur form:以下BNFと略す)による文脈自由文法(context-free grammer)です[*1]。

ま、ざっくり言えば、yaccがやってくれることは、 テトリスのようなもんだと思ってください。

まず、yaccが生成したパーサは、内部的にスタックを保持しています。 このスタックに、 テトリスのブロックよろしくトークンが積み上がっていくことになります。

これは、前述の構文規則の右側と一致します。パーサーは、この規則を適用することによって入力を還元 (reduce) できます。
https://docs.oracle.com/cd/E19620-01/805-5827/6j5gframt/index.html

この規則を適用すると、入力は還元されて expr (規則の左側) になります。その後、パーサーは入力の最後の部分 (その部分を以下に示します) を読み取って、再度 reduce を実行します。

https://ist.ksc.kwansei.ac.jp/~ishiura/prevxcpl/yacc.pdf

書換規則 → 非終端記号 “:” 右辺列 “;”
右辺列 → 右辺 | 右辺 “|” 右辺列
右辺 → 記号列 “{” C言語 “}”
記号列 → 記号 | 記号 記号列
記号 → 非終端記号 | 終端記号

再起という概念

再帰は、YACC ではきわめて重要です。これなくしては、独立するコマンドや 文の連続からファイルが構成されている、ということが言えなくなります。つ まり、YACC にとって最も重要なのは一番目の規則、即ち、’%start’ シンボルで指定した、起点を示す規則のみということになります。

yylex関数

動作の中に return 文を入れておくと、 その式の値が Flex の生成する yylex 関数の戻り値になります。 yylex 関数は呼び出されるたびに、次のトークンを返します。

yylval 意味値

yaccでuniconで定義した変数は、lexで、yylval.変数名で参照できます。

bison側ではflex側で解析した結果を$1とか$2という変数で参照することができます。ただそのためには、%union型の変数を使って渡す宣言(と先述したflex側でのデータ設定処理)が必要です。

yylvalをunionにし、その中に型の異なる変数を含める。

終端記号に対しては、字句解析ルーチ ンyylexからは、yylexの値をNUM,SYMを返すとともに、意味値をyylvalという 変数(これはyaccから生成されるルーチンの中で定義されている)を介して、 意味値を返す。

yaccではchar型の配列に保持されています。またその文字列の長さはyylengに格納されています。これら二つの変数は,字句解析中に常時書き換えられていますので、マッチしたら即座にアクション中で別の変数(大域変数)に保存しておくなどすれば、構文解析中でも利用することができます。

Flex が出力する Cコードの中で yylval変数 が使えるようにするために yylex の定義を変えてやる必要があります。
それには Flex 側で YY_DECLマクロを定義します。

bison/yacc

https://matome.naver.jp/odai/2137764196894476501
2019年08月15日