コンパイラの設計-正規表現

字句解析プログラムは、手元の言語に属する有効な文字列/トークン/語彙素の有限セットのみをスキャンして識別する必要があります。言語ルールで定義されたパターンを検索します。

正規表現には、シンボルの有限文字列のパターンを定義することにより、有限言語を表現する機能があります。正規表現で定義された文法は、*通常の文法*として知られています。通常の文法で定義されている言語は、「通常の言語」として知られています。

正規表現は、パターンを指定するための重要な表記法です。各パターンは一連の文字列と一致するため、正規表現は一連の文字列の名前として機能します。プログラミング言語トークンは、通常の言語で記述できます。正規表現の仕様は、再帰的な定義の例です。通常の言語は理解しやすく、効率的に実装されています。

正規表現に従ういくつかの代数則があり、正規表現を同等の形式に操作するために使用できます。

オペレーション

言語のさまざまな操作は次のとおりです。

2つの言語LとMの和は、 + L U M = \ {s | sはLにあり、sはMにあります}
2つの言語LとMの連結は、 + LM = \ {st | sはLに、tはMにあります} 言語Lのクリーネ閉包は、 + L =言語Lの0回以上の出現。

表記法

rとsが言語L（r）とL（s）を表す正規表現である場合、

Union ：（r）|（s）は、L（r）U L（s）を表す正規表現です
連結：（r）（s）は、L（r）L（s）を表す正規表現です
* Kleeneクロージャ*：（r）*は（L（r））*を表す正規表現です
（r）はL（r）を表す正規表現です

優先順位と結合性

*、連結（。）、および| （パイプ記号）は連想的に残されます
*優先度が最も高い
連結（。）が2番目に高い優先順位を持っています。
| （パイプ記号）は、すべての優先順位が最も低くなります。

正規表現で言語の有効なトークンを表す

xが正規表現の場合：

 *x* は、0回以上のxの出現を意味します。
+つまり、\ {e、x、xx、xxx、xxxx、…}を生成できます
 *x +は、1つ以上のxの出現を意味します。
+つまり、\ {x、xx、xxx、xxxx…}またはx.x* を生成できます
* x? xの最大1回の出現を意味します
+つまり、\ {x}または\ {e}を生成できます。

正規表現を使用してシンボルの出現を表現する

文字= [a – z]または[A – Z]

桁= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9または[0-9]

記号= [+ | -]

正規表現を使用した言語トークンの表現

10進数=（符号）^？（桁）^ + ^

識別子=（文字）（文字|数字）*

字句解析器に残された唯一の問題は、言語のキーワードのパターンを指定する際に使用される正規表現の有効性を検証する方法です。広く受け入れられているソリューションは、検証に有限オートマトンを使用することです。

Compiler-design-regular-expressions

目次