語法分析

• 簡介
  

  語法分析簡介.png

• 上下文無關(guān)語法

  • 形式化(只是個例子)

         S -> N V N
         N -> s | t | g | w
         V -> e | d
         非終結(jié)符:{S,N,V}
         終結(jié)符:{s,t,g,w,e,d}
         開始符號:{S}
    

  • 嚴(yán)格的數(shù)學(xué)定義

         G = {T,N,P,S}
         T為終結(jié)符集合,
         N為非終結(jié)符集合,
         P是一組產(chǎn)生式規(guī)則,
         S是唯一的開始符號;
    

  • BNF范式

    • <E>:非終結(jié)符
    • 下劃線:終結(jié)符

  • 分析樹

  • 二義性文法

• 自頂向下分析(逐個嘗試)

  • 自頂向下

         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)
             }
         }
    

  • 遞歸下降分析算法

    • 遞歸實現(xiàn)讀取

           parse_S(){
               parse_N();
               parse_V();
               parse_N();
           }
           parse_N(){
               token = tokens[i++];
               if(token==s||token==t||token==g||token==w){
                   return//識別了就直接return并且上面已經(jīng)i++了
               }
               error();
           }
           parse_V(){}
      

    • 遞歸實現(xiàn)識別算術(shù)運算符
      

      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)推導(dǎo),采用一個(1)前看符號

    • LL(1)分析表
      • 根據(jù)前看符號來判斷,就是tokens中現(xiàn)在指針指向的元素.
      • 分析表.png
      • 上下文無關(guān)文法.png

      • 棧執(zhí)行順序圖
        計算1.JPG
    • LL(1)表中的沖突
      • LL(1)分析表中一個非終結(jié)符對應(yīng)了兩種
      • NULLABLE表的構(gòu)建:
        
        NULLABLE.png
      • FIRST集合的完整計算公式
        
        FIRST集合計算公式.png

• 自底向上算法

  • LR分析算法