Next: , Previous: Table of Symbols, Up: Top


Appendix 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 Lexical Tie-ins
Literal string token(リテラル文字列トークン)
2文字以上の決まった文字列からなるトークンです。 See Symbols
Look-ahead token(先読みトークン)
すでに読み込まれていて、シフトされていないトークンです。 See Look-Ahead Tokens
LALR(1)
Bison(または似ているほとんどの構文解析器)によって扱える、 文脈自由文法の一部分で、LR(1)の部分集合です。 See Mysterious Reduce/Reduce Conflicts
LR(1)
任意の入力のあいまいでない構文解析に対して、 単に1個の先読みトークンを必要とするような、 文脈自由文法の一部分です。
Nonterminal symbol(非終端記号)
文法的構成要素を表す文法記号で、文法規則によってより小さな構成要素に 分解できるものです。言い換えると、トークンでない構成要素です。 See Symbols
Parse error(構文エラー)
入力ストリームを構文解析しているときに、誤った文法によって発生するエラーです。 See Error Recovery
Parser(構文解析器)
字句解析器から渡されたトークンの集合の文法的構造を解析して、 言語の有効な文を認識する関数です。
Postfix operator(後置演算子)
演算の対象のオペランドの後に置かれる算術演算子です。
Reduction(還元)
文法規則に従って、非終端記号または終端記号の列を、 1個の非終端記号に置き換えることです。 See The Bison Parser Algorithm
Reentrant(再入可能)
再入可能な手続きとは、複数の呼び出しの間での相互作用なしに、 並行して任意の数を呼び出せる手続きです。 1 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文字リテラル)
そのままに解釈される21文字です。 See From Formal Rules to Bison Input
Start symbol(開始記号)
構文解析された有効な言語の全体を表す非終端記号です。 通常、言語仕様に書かれた最初の非終端記号です。 See The Start-Symbol
Symbol table(記号表)
繰り返し使われる記号の情報を認識して使うために、 構文解析の途中で、記号の名前と関連する情報を記憶するデータ構造です。 See Multi-function Calc
Token(トークン)
言語の、基本的で、文法的に分割できない単位です。 文法の中のトークンを記述する記号を終端記号といいます。 Bison構文解析器の入力は、字句解析器からの、 トークンの流れです。 See Symbols
Terminal symbol(終端記号)
文法規則を持たず、したがって文法的に分割できない文法記号です。 これが表す文字の集まりをトークンといいます。 See Languages and Context-Free Grammars

Footnotes

[1] 【訳注】ある関数が終了する前に、 その同じ関数を非同期に呼び出してもよいということ。

[2] 【訳注】字句解析器によって