C＃でトップダウンパーサーを実装する

Question

私は学生で、私はC＃言語を使用して開発された言語変換プロジェクトでトップダウンパーサーを実装したいと考えています。たとえば、 "私の名前はHusniで、私は学生です"という文のパーサーツリーを構築する必要がある場合、C＃言語でどのようにすればいいですか？

Answer 1

この本の後には、コンパイラジェネレータについても、コンパイラの作成に役立つ（C＃でも）視覚的にも役立つANTLRと読むことができます。

Answer 2

私は非常にこの本をお勧めします。

Basics of Compiler Design

あなたは自由のためのPDFファイルをダウンロードすることができます。これは、あなたの背景について過度の前提を持たせることなく、包括的な方法で解析（上から下、下から上へ）をカバーします。

非常に読みやすい。

C＃のやり方は？あなたが他の言語でやっているのと同じように、C＃の構文を使うだけです。理論を学ぶとコードは自然に来る。

Answer 3

あなたはANTLRをインストール：http://www.antlr.org/

形式文法仕様からトップダウン再帰下降パーサを生成偉大なコンパイラ構築ツール。

そして、あなたはテランスパーの本のコピーを取得：

• The Definitive ANTLR Reference: Building Domain-Specific Languages（2007）
• Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages（2009）

もう一つの選択肢はIrony.Netされます：http://irony.codeplex.com/

を Ironyは、.NETプラットフォームで言語を実装するための開発キットです。 orm。ほとんどの既存のyacc/lexスタイルのソリューションとは異なり、Ironyは特殊なメタ言語で書かれた文法仕様からスキャナやパーサコード生成を使用しません。アイロニーでは、ターゲット言語文法は、演算子のオーバーロードを使用してC＃で直接コーディングされ、文法構成を表現します。 Ironyのスキャナとパーサモジュールは、解析プロセスを制御するためにc＃クラスとしてエンコードされた文法を使用します。

は、ここで算術式を解析するためのサンプルアイロニー表現文法です：

using System; 
using System.Collections.Generic; 
using System.Text; 
using Irony.Parsing; 
using Irony.Ast; 

namespace Irony.Samples 
{ 
    // This grammar describes programs that consist of simple expressions and assignments 
    // for ex: 
    // x = 3 
    // y = -x + 5 
    // the result of calculation is the result of last expression or assignment. 
    // Irony's default runtime provides expression evaluation. 
    // supports inc/dec operators (++,--), both prefix and postfix, 
    // and combined assignment operators like +=, -=, etc. 

    [Language("ExpressionEvaluator", "1.0", "Multi-line expression evaluator")] 
    public class ExpressionEvaluatorGrammar : Irony.Parsing.Grammar 
    { 

    public ExpressionEvaluatorGrammar() 
    { 

     // 1. Terminals 
     var number = new NumberLiteral("number"); 

     //Let's allow big integers (with unlimited number of digits): 
     number.DefaultIntTypes = new TypeCode[] { TypeCode.Int32, TypeCode.Int64, NumberLiteral.TypeCodeBigInt }; 
     var identifier   = new IdentifierTerminal("identifier"); 
     var comment   = new CommentTerminal("comment", "#", "\n", "\r"); 

     //comment must to be added to NonGrammarTerminals list; it is not used directly in grammar rules, 
     // so we add it to this list to let Scanner know that it is also a valid terminal. 
     base.NonGrammarTerminals.Add(comment); 

     // 2. Non-terminals 
     var Expr   = new NonTerminal("Expr"); 
     var Term   = new NonTerminal("Term"); 
     var BinExpr  = new NonTerminal("BinExpr", typeof(BinExprNode)); 
     var ParExpr  = new NonTerminal("ParExpr"); 
     var UnExpr   = new NonTerminal("UnExpr", typeof(UnExprNode)); 
     var UnOp   = new NonTerminal("UnOp"); 
     var BinOp   = new NonTerminal("BinOp", "operator"); 
     var PostFixExpr = new NonTerminal("PostFixExpr", typeof(UnExprNode)); 
     var PostFixOp  = new NonTerminal("PostFixOp"); 
     var AssignmentStmt = new NonTerminal("AssignmentStmt", typeof(AssigmentNode)); 
     var AssignmentOp = new NonTerminal("AssignmentOp", "assignment operator"); 
     var Statement  = new NonTerminal("Statement"); 
     var ProgramLine = new NonTerminal("ProgramLine"); 
     var Program  = new NonTerminal("Program", typeof(StatementListNode)); 

     // 3. BNF rules 
     Expr.Rule   = Term | UnExpr | BinExpr | PostFixExpr; 
     Term.Rule   = number | ParExpr | identifier; 
     ParExpr.Rule  = "(" + Expr + ")"; 
     UnExpr.Rule   = UnOp + Term; 
     UnOp.Rule   = ToTerm("+") | "-" | "++" | "--"; 
     BinExpr.Rule  = Expr + BinOp + Expr; 
     BinOp.Rule   = ToTerm("+") | "-" | "*" | "/" | "**"; 
     PostFixExpr.Rule = Term + PostFixOp; 
     PostFixOp.Rule  = ToTerm("++") | "--"; 
     AssignmentStmt.Rule = identifier + AssignmentOp + Expr; 
     AssignmentOp.Rule = ToTerm("=") | "+=" | "-=" | "*=" | "/="; 
     Statement.Rule  = AssignmentStmt | Expr | Empty; 
     ProgramLine.Rule = Statement + NewLine; 
     Program.Rule  = MakeStarRule(Program, ProgramLine); 
     this.Root   = Program;  // Set grammar root 

     // 4. Operators precedence 
     RegisterOperators(1, "+", "-"); 
     RegisterOperators(2, "*", "/"); 
     RegisterOperators(3, Associativity.Right, "**"); 

     // 5. Punctuation and transient terms 
     RegisterPunctuation("(", ")"); 
     RegisterBracePair("(", ")"); 
     MarkTransient(Term, Expr, Statement, BinOp, UnOp, PostFixOp, AssignmentOp, ProgramLine, ParExpr); 

     //automatically add NewLine before EOF so that our BNF rules work correctly when there's no final line break in source 
     this.LanguageFlags = LanguageFlags.CreateAst | LanguageFlags.NewLineBeforeEOF | LanguageFlags.CanRunSample; 

    } 

    } 

}//namespace 

第三の選択肢は、本質的にLINQのを使用して、C＃でNParsec、HaskellのParsecの（モナドパーサコンビネータ—のC＃のポートのようなものを使用することですRxのパーサのようなhttp://www.haskell.org/haskellwiki/Parsec#Parsec_clones_in_other_languages、または他のそのようなライブラリ：書き込むためのパーサ）http://rxx.codeplex.com/wikipage?title=Parsers

もっとここモナドパーサコンビネータ上：

• http://mikehadlow.blogspot.com/2011/01/monads-in-c1-introduction.html
• http://devhawk.net/2008/07/31/monadic-philosophy-part-3-the-parser-monad-in-c/
• http://stevegilham.blogspot.com/2011/01/monadic-parsers-in-c.html

Answer 4

あなたは曖昧である自然言語を解析しようとしています。これは、パーサーが文のために複数の解析木を許可することを意味します。だから、私はANTLRのような規則的な言語設計ツールが助けになるとは思わない。

私はPEPトップダウンダイナミックCFGパーサーを使用しています。それはJavaで書かれています。それをC＃に移植すると、新しいものを一から書くよりも簡単になります。