形式言語と式の表現

本単元は、プログラムや数式を機械が誤りなく読み取るために、記号の並びに決まりを与える形式言語の考え方と、式の表し方を扱う。形式言語とは、記号列のうち文法規則に従うものだけを言語の要素とみなす枠組みである。式の記法、プログラム言語の構文、そしてある記号列が決まりに合うかを判定する機械であるオートマトンは、いずれもこの考え方の上に成り立っている。

言語処理の段階と形式言語

手続型言語の処理系は、字句解析、構文解析、意味解析、最適化、コード生成の順に作業を進める。字句解析はソースコードを語の並びに分ける段階であり、構文解析は語の並びが文法規則に合うかを判定して構文木を作る。意味解析は変数の型や宣言の整合性を確かめる段階である。字句解析はソースコード処理の最初の段階に置かれる。 コード生成の直前に行う処理は最適化であり、意味解析や構文解析より後段に位置する。

式の記法と後置記法の評価

式 A＋B×C は、演算子を被演算子の間に置く中置記法で書かれる。この記法では掛け算を先に行うという優先順位の規則を読み手が補う必要がある。逆ポーランド表記法（後置記法）は、演算子を被演算子の後ろに置くことで、括弧や優先順位の規則を使わずに演算の順序を文字列の並びそのものに表す。A＋B×C を後置記法で表すには、A、B、C を順に並べ、BとCを掛ける×を先に、Aと加える＋を後に置く。 同じ式で、演算子を被演算子より前に置いた並びは後置記法として成立しない。

後置記法の値は、左から順に読み、被演算子を一時的に積んでおき、演算子を読んだ時点で直前の二つの値に演算を施すことで求める。この方法では括弧の対応を追う必要がない。例えば、A、B、C、Dに数値を当てはめ、減算、乗算、加算を並べた式では、先に読まれた減算の結果が乗算に渡り、最後に加算で完成する。 演算子の位置を機械的にたどれるため、後置記法は処理系が式を評価する際の中間表現として用いられる。