语法分析

语法分析

• 简介
  

  语法分析简介.png

• 上下文无关语法

  • 形式化(只是个例子)

         S -> N V N
         N -> s | t | g | w
         V -> e | d
         非终结符:{S,N,V}
         终结符:{s,t,g,w,e,d}
         开始符号:{S}
    

  • 严格的数学定义

         G = {T,N,P,S}
         T为终结符集合,
         N为非终结符集合,
         P是一组产生式规则,
         S是唯一的开始符号;
    

  • BNF范式

    • <E>:非终结符
    • 下划线:终结符

  • 分析树

  • 二义性文法

• 自顶向下分析(逐个尝试)

  • 自顶向下

         tokens[]//输入的字符串
         i=0
         stack=[s]//栈
         while(stack!=[]){
             if(stack[top] is a terminal t){
                 if(t==tokens[i++]){
                     pop()
                 }else{
                     backtrack()
                 }
             }else if(stack[top] is a nonterminal T){
                 pop()
                 push(the next right hand side of T)
             }
         }
    

  • 递归下降分析算法

    • 递归实现读取

           parse_S(){
               parse_N();
               parse_V();
               parse_N();
           }
           parse_N(){
               token = tokens[i++];
               if(token==s||token==t||token==g||token==w){
                   return//识别了就直接return并且上面已经i++了
               }
               error();
           }
           parse_V(){}
      

    • 递归实现识别算术运算符
      

      Recursive descent algorithm.png

          parse_E(){
              parse_T();
              token = tokens[i++];
              while (token==+){
                  parse_T();
                  token = tokens[i++];
              }
          }
          parse_T(){
              parse_F();
              token = tokens[i++];
              while(token==*){
                  parse_F();
                  token = tokens[i++];
              }
          }
      

  • LL(1)分析算法

    从左(L)向右读入程序,最左(L)推导,采用一个(1)前看符号

    • LL(1)分析表
      • 根据前看符号来判断,就是tokens中现在指针指向的元素.
      • 分析表.png
      • 上下文无关文法.png
      • 栈执行顺序图 计算1.JPG
    • LL(1)表中的冲突
      • LL(1)分析表中一个非终结符对应了两种
      • NULLABLE表的构建:
        NULLABLE.png
      • FIRST集合的完整计算公式
        FIRST集合计算公式.png

• 自底向上算法

  • LR分析算法