B. 用語集

Backus-Naur Form（BNF）（バッカス-ナウア記法）

文脈自由文法を形式的に表現する方法です。 BNFは、1963年の報告

ALGOL-60

で初めて使われました。 See 節 Languages and Context-Free Grammars。

Context-free grammars（文脈自由文法）

文脈に関係なく適用される規則によって定められる文法です。 したがって、もし、整数は式として使われてもよいという規則があれば、 式が許されるあらゆる場所で整数の利用が許されます。 See 節 Languages and Context-Free Grammars。

Dynamic allocation（動的割り当て）

プログラムをコンパイルするときでも、関数の実行を始めるときでもなく、 実行の途中でメモリを割り当てることです。

Empty string（空文字列）

集合論での空集合と同様に、空文字列とは長さが0の文字列です。

Finite-state stack machine（有限状態スタック機械）

その完全な状態が、各瞬間での状態で記述される「機械」です。 機械への入力が処理されると、機械の論理に応じて、 機械の状態が別の状態に変わります。 本書では、入力とは構文解析されている言語で、 状態とは文法規則のさまざまな段階です。 See 節 The Bison Parser Algorithm 。

Grouping（グループ）

言語の構成要素で、（一般的に）文法的に分割可能なのもです。 たとえば、C言語の「式」や「宣言」です。 See 節 Languages and Context-Free Grammars。

Infix operator（中間記法演算子）

演算の対象となるオペランドの中間に置かれる算術演算子です。

Input stream（入力ストリーム）

入出力装置またはプログラムの間での、連続的なデータの流れです。

Language construct（言語構文）

言語の概要を示す典型的な方法の1つです。 たとえば、C言語の構文の1つはif文です。 See 節 Languages and Context-Free Grammars。

Left associativity（左結合性）

左結合性を持つ演算子は、左から右に向かって構文解析されます。 たとえば、`a+b+c'では、まず`a+b'が計算され、 次に`c'との和が計算されます。 See 節 Operator Precedence。

Left recursion（左再帰）

結果の記号が構成要素の最初の記号と等しいような規則です。 たとえば、`expseq1 : expseq1 ',' exp;'が左再帰です。 See 節 Recursive Rules。

Left-to-right parsing（LR構文解析）

左側から右側に向かって、トークンを次々に解析していくような、 言語の構文解析方法です。 See 節 The Bison Parser Algorithm 。

Lexical analyzer（scanner）（字句解析器）

入力ストリームを読んで、トークンを1つずつ返す関数です。 See 節 The Lexical Analyzer Function yylex。

Lexical tie-in（字句解析結び付き）

文法規則によって設定されるフラグが、トークンが字句解析される方法に 影響することです。 See 節 7.2 字句解析結び付き。

Literal string token（リテラル文字列トークン）

2文字以上の決まった文字列からなるトークンです。 See 節 3.2 記号、終端と非終端。

Look-ahead token（先読みトークン）

すでに読み込まれていて、シフトされていないトークンです。 See 節 Look-Ahead Tokens。

LALR(1)

Bison（または似ているほとんどの構文解析器）によって扱える、 文脈自由文法の一部分で、LR(1)の部分集合です。 See 節 Mysterious Reduce/Reduce Conflicts。

LR(1)

任意の入力のあいまいでない構文解析に対して、 単に1個の先読みトークンを必要とするような、 文脈自由文法の一部分です。

Nonterminal symbol（非終端記号）

文法的構成要素を表す文法記号で、文法規則によってより小さな構成要素に 分解できるものです。言い換えると、トークンでない構成要素です。 See 節 3.2 記号、終端と非終端。

Parse error（構文エラー）

入力ストリームを構文解析しているときに、誤った文法によって発生するエラーです。 See 節 6. エラーからの回復。

Parser（構文解析器）

字句解析器から渡されたトークンの集合の文法的構造を解析して、 言語の有効な文を認識する関数です。

Postfix operator（後置演算子）

演算の対象のオペランドの後に置かれる算術演算子です。

Reduction（還元）

文法規則に従って、非終端記号または終端記号の列を、 1個の非終端記号に置き換えることです。 See 節 The Bison Parser Algorithm 。

Reentrant（再入可能）

再入可能な手続きとは、複数の呼び出しの間での相互作用なしに、 並行して任意の数を呼び出せる手続きです。 (16) See 節 A Pure (Reentrant) Parser。

Reverse polish notation（逆ポーランド記法）

すべての演算子が後置記法演算子であるような言語です。

Right recursion（右再帰）

規則の結果の記号が、規則の最後の構成要素と同じ記号であるような規則です。 たとえば、`expseq1: exp ',' expseq1;'は右再帰です。 See 節 Recursive Rules.

Semantics（意味）

計算機言語では、言語の各インスタンスが起こすアクションによって、 意味が指定されます。すなわち、各文の意味です。 See 節 Defining Language Semantics。

Shift（シフト）

構文解析器がシフトするとは、 すでに認識されているある規則によってただちに還元する代わりに、 ストリームからのさらなる入力を分析することです。 See 節 The Bison Parser Algorithm 。

Single-character literal（1文字リテラル）

そのままに解釈される(17)1文字です。 See 節 From Formal Rules to Bison Input。

Start symbol（開始記号）

構文解析された有効な言語の全体を表す非終端記号です。 通常、言語仕様に書かれた最初の非終端記号です。 See 節 The Start-Symbol。

Symbol table（記号表）

繰り返し使われる記号の情報を認識して使うために、 構文解析の途中で、記号の名前と関連する情報を記憶するデータ構造です。 See 節 2.4 多機能電卓：mfcalc。

Token（トークン）

言語の、基本的で、文法的に分割できない単位です。 文法の中のトークンを記述する記号を終端記号といいます。 Bison構文解析器の入力は、字句解析器からの、 トークンの流れです。 See 節 3.2 記号、終端と非終端。

Terminal symbol（終端記号）

文法規則を持たず、したがって文法的に分割できない文法記号です。 これが表す文字の集まりをトークンといいます。 See 節 Languages and Context-Free Grammars。