コンパイラ文法曖昧化設計
3328 ワード
コンパイル理論では、コンパイルプロセスは、一般に、文法解析(Lexical Analysis)、構文解析(Parsing)、意味解析(Semantic Analysis)、最適化(Optimization)、コード生成(Code Generation)の5つの主要段階に抽象化される.この5つのフェーズはUnixパイプモデルに類似しており,前のフェーズの出力は次のフェーズの入力として用いられる.ここで,語法解析は,入力元コードのテキストストリームに基づいて,語を分割し,カテゴリを識別し,語法要素(Token)ストリームを生成する.
構文解析によって[(Type,"int"),(Identifier,"a"),(AssignOperator,"="),(IntLiteral,10)]が得られ,後続の構文解析段階ではこれらの構文要素に基づいて対応する構文規則が一致する.私がコンパイル原理を学ぶとき、教科書の中で文法分析の紹介は主に正規表現に基づいており、普通の言語の文法規則は正規表現で記述できることを意味している.たとえば、C言語の変数名規則は「アルファベット、数字、下線を含み、アルファベットまたは下線で始まる」であり、これは正規表現
上のコードはC++98コンパイラに文法の間違いを報告されます.なぜなら、「>>」を2つのテンプレートの右かっこではなく、ビット右シフト演算子として認識し、C++98では2つのカッコの間にスペースを付けて書かなければなりません.
C++テンプレートを除いて、私の知っている限りでは、古典的なFORTRAN言語の文法規則には文法の曖昧さが多く存在しています.
本質的に言えば、このような問題の根源は文法分析の根拠が簡単な文法規則にすぎず、すべての文法情報を備えていないが、文法の曖昧さは文法規則の中で解消しなければならないと考えている.だから、私自身がDSLを設計する時、いっそ文法分析と文法分析を一つにして、文法分析を文字の階層で行うことに相当して、経典の文法要素の階層ではありませんて、これはいわゆるScannerless Parsingです.この方法を採用する例は珍しくないが,TeX,Wiki,Makefile,Perl 6などの言語の構文解析器はいずれもこのようなものである.
Scannerless Parsing法は,文法規則が曖昧にならないという問題を補うが,文法解析が簡単で明瞭なパイプ構造を破壊し,全体的に実現と理解の複雑さを増した.また、C++のような大きな言語では、最初は語法分析があったのであれば、少し曖昧さにぶつかってScannerless Parsingに全体的に転換するのは大げさすぎる.この問題は長い間困っていたが,最近になってやっと満足のいく解決策を見つけた.それとも上の「>>」を例にとると、C++11はスペースを追加しないことを許可していることがわかりますが、C++11コンパイラはこの語法の曖昧さをどのように処理しているのでしょうか.答えは:文法分析の段阶で分析がうまくいかない以上、いっそ分析しないで、直接">""を文法分析器に渡して分析して、その他の文法の违いがないのはやはりです.私がこの案を知ったとき、思わず感嘆しました.理論上、文法分析は何もしなくてもいいので、すべての文字を文法分析器に渡しても問題ありません.だから、いっそ文法分析を把握している部分だけをして、解決できないのは文法分析器に渡して、このようにパイプ構造を残して、文法の曖昧さを解決しました.
次に、C++11仕様のこの問題の定義を見てみましょう.
14.2 Names of template specializations [temp.names] ###
After name lookup (3.4) finds that a name is a template-name or that an operator-function-id or a literal-operator-id refers to a set of overloaded functions any member of which is a function template if this is followed by a <, the < is always taken as the delimiter of a template-argument-list and never as the less-than operator. When parsing a template-argument-list, the first non-nested > is taken as the ending delimiter rather than a greater-than operator. Similarly, the first non-nested >> is treated as two consecutive but distinct > tokens, the first of which is taken as the end of the template-argument-list and completes the template-id. [ Note: The second > token produced by this replacement rule may terminate an enclosing template-id construct or it may be part of a different construct (e.g. a cast).—end note ]
C++11では、構文解析器が">>"を直接2つの">"として構文解析器に渡し、構文解析でtemplate-argument-lis構文に一致すると、最初の">"記号は、より大きくなく、シフト記号ではなく、テンプレートの終了記号として直接認識されます.この定義に基づいて、私は例を構築しました.
この例はC++98で正しくコンパイルでき、">>"はシフト演算として解釈されるが、逆にC++11でコンパイルできない.仕様に従って最初の">"はテンプレートパラメータ終了子として解釈されるからである.C++11でコンパイルする場合は、カッコを明示的に付ける必要があります.
int a = 10;
構文解析によって[(Type,"int"),(Identifier,"a"),(AssignOperator,"="),(IntLiteral,10)]が得られ,後続の構文解析段階ではこれらの構文要素に基づいて対応する構文規則が一致する.私がコンパイル原理を学ぶとき、教科書の中で文法分析の紹介は主に正規表現に基づいており、普通の言語の文法規則は正規表現で記述できることを意味している.たとえば、C言語の変数名規則は「アルファベット、数字、下線を含み、アルファベットまたは下線で始まる」であり、これは正規表現
[a-zA-Z_][a-zA-Z0-9_]*で表すことができる.しかし、実際には主流言語でも、自分で設計したDSLでも、簡単に正規表現で文法分析ができない例がたくさんあることに気づきました.C++98テンプレートの例を見てみましょう.map<int, vector<int>>
上のコードはC++98コンパイラに文法の間違いを報告されます.なぜなら、「>>」を2つのテンプレートの右かっこではなく、ビット右シフト演算子として認識し、C++98では2つのカッコの間にスペースを付けて書かなければなりません.
map<int, vector<int> >
C++テンプレートを除いて、私の知っている限りでは、古典的なFORTRAN言語の文法規則には文法の曖昧さが多く存在しています.
本質的に言えば、このような問題の根源は文法分析の根拠が簡単な文法規則にすぎず、すべての文法情報を備えていないが、文法の曖昧さは文法規則の中で解消しなければならないと考えている.だから、私自身がDSLを設計する時、いっそ文法分析と文法分析を一つにして、文法分析を文字の階層で行うことに相当して、経典の文法要素の階層ではありませんて、これはいわゆるScannerless Parsingです.この方法を採用する例は珍しくないが,TeX,Wiki,Makefile,Perl 6などの言語の構文解析器はいずれもこのようなものである.
Scannerless Parsing法は,文法規則が曖昧にならないという問題を補うが,文法解析が簡単で明瞭なパイプ構造を破壊し,全体的に実現と理解の複雑さを増した.また、C++のような大きな言語では、最初は語法分析があったのであれば、少し曖昧さにぶつかってScannerless Parsingに全体的に転換するのは大げさすぎる.この問題は長い間困っていたが,最近になってやっと満足のいく解決策を見つけた.それとも上の「>>」を例にとると、C++11はスペースを追加しないことを許可していることがわかりますが、C++11コンパイラはこの語法の曖昧さをどのように処理しているのでしょうか.答えは:文法分析の段阶で分析がうまくいかない以上、いっそ分析しないで、直接">""を文法分析器に渡して分析して、その他の文法の违いがないのはやはりです.私がこの案を知ったとき、思わず感嘆しました.理論上、文法分析は何もしなくてもいいので、すべての文字を文法分析器に渡しても問題ありません.だから、いっそ文法分析を把握している部分だけをして、解決できないのは文法分析器に渡して、このようにパイプ構造を残して、文法の曖昧さを解決しました.
次に、C++11仕様のこの問題の定義を見てみましょう.
14.2 Names of template specializations [temp.names] ###
After name lookup (3.4) finds that a name is a template-name or that an operator-function-id or a literal-operator-id refers to a set of overloaded functions any member of which is a function template if this is followed by a <, the < is always taken as the delimiter of a template-argument-list and never as the less-than operator. When parsing a template-argument-list, the first non-nested > is taken as the ending delimiter rather than a greater-than operator. Similarly, the first non-nested >> is treated as two consecutive but distinct > tokens, the first of which is taken as the end of the template-argument-list and completes the template-id. [ Note: The second > token produced by this replacement rule may terminate an enclosing template-id construct or it may be part of a different construct (e.g. a cast).—end note ]
C++11では、構文解析器が">>"を直接2つの">"として構文解析器に渡し、構文解析でtemplate-argument-lis構文に一致すると、最初の">"記号は、より大きくなく、シフト記号ではなく、テンプレートの終了記号として直接認識されます.この定義に基づいて、私は例を構築しました.
template<int N>
class Foo {
}
Foo<3>>1> foo;
この例はC++98で正しくコンパイルでき、">>"はシフト演算として解釈されるが、逆にC++11でコンパイルできない.仕様に従って最初の">"はテンプレートパラメータ終了子として解釈されるからである.C++11でコンパイルする場合は、カッコを明示的に付ける必要があります.
Foo<(3>>1)> foo;