一个编译器的实现3——用编译原理自动化制作文本解析器

PS：。

 

关于编译器的概念、工作流程、算法和设计方案，可参考这里（）。阅读本文须理解“上下文无关文法（Context-free Grammar）”是什么。

本文以加减乘除表达式和一个3D坦克游戏模型为例，说明如何自动生成解析器以及如何使用自动生成的代码。

文末附源代码。

加减乘除表达式

运行编译器代码生成器（bitzhuwei.CGCompiler.Winform.exe），默认配置文件中已经有加减乘除表达式（Expression）的文法了。

设置好编译器名字、命名空间和代码存放的位置，点击“开始！”。

若文法没有错误，会在指定位置生成Expression解析器的代码。

一共生成了10个文件（其中bitzhuwei.CompilerBase.dll和使用说明.txt是直接复制的）。

三个Enum*.cs文件分别是文法的字符类型、单词类型和语法树结点类型。

LexicalAnalyzer*.cs文件是词法分析器。

LL1SyntaxParser*.cs文件是语法分析器。

SyntaxTreeNodeValue*.cs文件是语法树结点类型，稍候会用到。

使用生存的代码的方法很简单：创建一个类库项目，把生成的10个文件全部加进去，引用bitzhuwei.CompilerBase.dll文件。

为了测试，再创建一个Console项目，用下面的代码测试。

测试Expression的代码        static void Main(string[] args)        {            var sourceCodes = new string[]            {                "37",                "19 * 19 - 18 * 18",                "(19 + 18) * (19 - 18)",            };            foreach (var sourceCode in sourceCodes)            {                var lex = new bitzhuwei.ExpressionCompiler.LexicalAnalyzerExpression();                lex.SetSourceCode(sourceCode);                var tokens = lex.Analyze();                Console.WriteLine(tokens);                var parser = new bitzhuwei.ExpressionCompiler.LL1SyntaxParserExpression();                parser.SetTokenListSource(tokens);                var tree = parser.Parse();                Console.WriteLine(tree);                var value = tree.GetValue();                Console.WriteLine(value);            }        }

 

输入的语法树如下图所示。

我们使用解析器，目的是为了得到数据结构后再获取有价值的结果。Expression的价值在于获取表达式的值，通过遍历语法树获取这个值是很容易的。（这个代码只能自己写，这属于语义分析阶段了，目前还无法自动生成。）

SyntaxTreeExpressionGetValue.cs/// 
    /// 提供SyntaxTree<EnumTokenTypeCG, EnumVTypeCG, SyntaxTreeNodeValueCG>的扩展方法    /// 
    public static partial class SyntaxTreeExpression    {        /// 
        /// 获取源代码的规范格式        /// 
      
       语法分析的副产品
              /// 
        /// 语法树        /// 
             public static double GetValue(this SyntaxTree
     
       tree)        {            if (tree == null) return double.NaN;            var tmpTree = tree.Clone() as SyntaxTree
      
       ;            _GetValue(tmpTree);            return double.Parse(tmpTree.Tag.ToString());        }        private static void _GetValue(SyntaxTree
       
         tree)        {            switch (tree.NodeValue.NodeType)            {                case EnumVTypeExpression.Unknown:                    break;                case EnumVTypeExpression.case_Expression://
        
          ::= 
          
          
           ; _GetValue(tree.Children[0]); _GetValue(tree.Children[1]); tree.Tag = double.Parse(tree.Children[0].Tag.ToString()) + double.Parse(tree.Children[1].Tag.ToString()); break; case EnumVTypeExpression.case_PlusOpt://
           
             ::= "+" 
            
              | "-" 
             
               | null; if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_PlusOpt___tail_plus_Leave()) { _GetValue(tree.Children[1]); tree.Tag = tree.Children[1].Tag; } else if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_PlusOpt___tail_minus_Leave()) { _GetValue(tree.Children[1]); tree.Tag = -double.Parse(tree.Children[1].Tag.ToString()); } else if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_PlusOpt___tail_rightParentheses_Leave() || tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_PlusOpt___tail_startEndLeave()) { tree.Tag = 0; } break; case EnumVTypeExpression.case_Multiply://
              
                ::= 
                
                
                 ; _GetValue(tree.Children[0]); _GetValue(tree.Children[1]); tree.Tag = double.Parse(tree.Children[0].Tag.ToString()) * double.Parse(tree.Children[1].Tag.ToString()); break; case EnumVTypeExpression.case_MultiplyOpt://
                 
                   ::= "*" 
                  
                    | "/" 
                   
                     | null; if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_MultiplyOpt___tail_multiply_Leave()) { _GetValue(tree.Children[1]); tree.Tag = double.Parse(tree.Children[1].Tag.ToString()); } else if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_MultiplyOpt___tail_divide_Leave()) { _GetValue(tree.Children[1]); tree.Tag = 1 / (double)tree.Children[1].Tag; } else if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_MultiplyOpt___tail_plus_Leave() || tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_MultiplyOpt___tail_minus_Leave() || tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_MultiplyOpt___tail_rightParentheses_Leave() || tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_MultiplyOpt___tail_startEndLeave()) { tree.Tag = 1; } break; case EnumVTypeExpression.case_Unit://
                    
                      ::= number | "(" 
                     
                       ")"; if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_Unit___numberLeave()) { tree.Tag = double.Parse(tree.Children[0].NodeValue.NodeName); } else if (tree.CandidateFunc == LL1SyntaxParserExpression.GetFuncParsecase_Unit___tail_leftParentheses_Leave()) { _GetValue(tree.Children[1]); tree.Tag = tree.Children[1].Tag; } break; default: break; } } }
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

ArmadaTank模型

坦克舰队（ArmadaTank）是我很喜欢的一款游戏，现在我正在试图用C#重写这个游戏。喜欢的同学可以自行搜索“坦克舰队”。

ArmadaTank的3D模型是用纯文本的*.dtm文件标识的。完全可以用自动生成的解析器来加载之。

步骤就不再说了，和Expression的步骤一样，这里只贴一下DTM文件的文法。

DTM的文法
     
       ::= "File" 
      
        "endfile";
       
         ::= "{
     " 
        
          "}";
         
           ::= 
           
           
             | null;
            
              ::= "FileDesc" 
             
               "endfiledesc" | "Faces" 
              
                | "MapChannel" 
                
                
                  | "Frame" 
                   "endframe";
                  
                    ::= "{ " 
                   
                     "}";
                    
                      ::= 
                      
                      
                        | null;
                       
                         ::= "Frames" 
                        
                          | "Vertices" 
                         
                           | "Faces" 
                          
                            | "Map" 
                           
                             "TVertices" 
                            
                             ;
                             
                               ::= "{ " 
                              
                                "}";
                               
                                 ::= 
                                 
                                 
                                   | null;
                                  
                                    ::= "Face" 
                                    
                                     
                                      
                                      
                                        "MatID" 
                                       
                                        ;
                                        
                                          ::= "{ " 
                                         
                                           "}";
                                          
                                            ::= 
                                            
                                            
                                              | null;
                                             
                                               ::= "TextureVertices" 
                                              
                                                | "TextureFaces" 
                                               
                                                ;
                                                
                                                  ::= "{ " 
                                                 
                                                   "}";
                                                  
                                                    ::= 
                                                    
                                                    
                                                      | null;
                                                     
                                                       ::= "TVertex" 
                                                       
                                                        
                                                         
                                                         
                                                          ;
                                                          
                                                            ::= "{ " 
                                                           
                                                             "}";
                                                            
                                                              ::= 
                                                              
                                                              
                                                                | null;
                                                               
                                                                 ::= "TFace" 
                                                                 
                                                                  
                                                                   
                                                                   
                                                                    ; ::= "{ " 
                                                                    
                                                                      "}";
                                                                     
                                                                       ::= 
                                                                       
                                                                       
                                                                         | null;
                                                                        
                                                                          ::= "Vertices" "{ " 
                                                                         
                                                                           "}";
                                                                          
                                                                            ::= 
                                                                            
                                                                            
                                                                              | null;
                                                                             
                                                                               ::= "Vertex" 
                                                                               
                                                                                
                                                                                 
                                                                                 
                                                                                  ;
                                                                                  
                                                                                    ::= "+" number | "-" number | number;
                                                                                  
                                                                                 
                                                                                
                                                                               
                                                                              
                                                                             
                                                                            
                                                                           
                                                                          
                                                                         
                                                                        
                                                                       
                                                                      
                                                                     
                                                                    
                                                                   
                                                                  
                                                                 
                                                                
                                                               
                                                              
                                                             
                                                            
                                                           
                                                          
                                                         
                                                        
                                                       
                                                      
                                                     
                                                    
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

用OpenGL来显示3D模型（语义分析及其之后的阶段），如下图所示。

源代码在此。