構文解析
一般的なプログラミング言語処理系や、簡単なサンプルによくあるいわゆる「電卓プログラム」などの場合を例として説明する。
まず第一段階として字句(トークン)を生成する。これを字句解析と呼ぶ。入力文字列は正規表現などによる定義に従い、意味のあるシンボルに分割される。例えば、電卓プログラムに "12*(3+4)^2" と入力されたとき、これを 12, *, (, 3, +, 4, ), ^, 2 という字句(トークン)に分割する。各トークンは電卓プログラムの数式として意味のあるシンボルである。字句解析を含む構文解析器は *, +, ^, (, ) といった文字が新たなトークンの先頭になるという規則を持っているため、"12*" や "(3" といった無意味な字句の切り分けは発生しない。
次の段階は狭義の構文解析である。トークンの並びが構文規則に照らして正しい表現となっているかを判定する。このため、構文規則を参照して再帰的に規則を適用していく。前述したように、構文規則で表現するのは現実的ではない言語上のルール、たとえば関数定義における仮引数名の重複などがあるので、そういったものへの対処も適宜実装する。
以上のように構文解析が終わった後に、意味的な解析が行われ、構文が確認された表現の意味を識別して、適当な行動をとる。電卓プログラムの場合、適当な行動とは式の評価(計算)であり、コンパイラならコードの生成である。
yaccなどでは属性文法的な考え方を活用し、トークン列に対するシフトや還元という解析の動作に対して実行すべきコード片を結び付け、それらのコード片により以上で説明したような処理を行う。