實驗一:javacc學習筆記

一、概念

JavaCC(Java Compiler Compiler)是一個用JAVA開發的受歡迎的文法分析生成器。這個分析生成器工具可以讀取上下文無關且有着特殊意義的文法并把它轉換成可以識别且比對該文法的JAVA程式。

JavaCC本身并不是一個詞法分析器或者解析器而是一個代碼生成器，這意味着它可以根據輸入的語言定義輸出一個詞法分析器和解析器。JavaCC輸出的代碼是合法的可編譯Java代碼。

詞法分析器工作流程：

文法分析器工作流程：

二、三個工具

javaCC 用來處理文法檔案（jj）生成解析代碼；

jjTree 用來處理jjt檔案，生成樹節點代碼和jj檔案，然後再通過javaCC生成解析代碼；

jjDoc 根據jj檔案生成bnf範式文檔（html）。這三個工具都十分重要，分别貫穿着編寫時的過程。

三、缺陷

javacc采用的是自頂向下的分析方法，而且沒有回溯功能，是以如何解決沖突的問題，是程式員的責任。

必須要解決兩個問題：左遞歸和公因子

關于左遞歸的問題，一般采用經典的修改文法的方法解決。

關于公因子的問題，可以改寫算法（提取公因子），也可以通過展望（look ahead）更多符号的方法來解決。 但是因為javacc擴充了經典的BNF，是以它面臨更多的問題。總之，當在編譯時碰到沖突問題時，就說到了一個choice point。

可以将javacc中choice point歸結為以下幾類：

l . 由選擇算子 | 引入的沖突，

2. 由可省略算子 [] 或 ？引入的沖突

3. 由重複算子 * 引入的沖突

4. 由重複算子 + 引入的沖突

當在javacc中碰到沖突時，可以采用下面的方法之一解決問題

修改文法，使之成為LL(1)文法。這個方法有一個問題：修改後的文法可能非常不直覺了

在jj檔案中給javacc一些提示。這些提示可以根據展望的作用域分成全局提示和部分提示。要采用全局提示，隻要将LOOKAHEAD=k寫到Options塊中即可（當然也可以寫到javacc的指令行裡），這樣javacc産生的分析器就可以分析LL(K)文法生成的語言。也可以設定一個局部的LOOKAHEAD，這樣既保持了LL(1)的高效性，又可以解決choice point中的。LOOKAHEAD的局部聲明形式是LOOKAHEAD(…)，其中括号中的可以是數字（說明向後看多少個記号），或者是一個表示文法的串（當成功時選擇）。LOOKAHEAD的完整形式為LOOKAHEAD(amount, expansion, {java語言裡的邏輯表達式})，它的含義是，如果到達amount個記号後，expansion如果仍然成立，且邏輯表達式也成立，則執行下面的展開。

采用第一種方法的好處是效率非常高，易于維護。采用第二種方法的好處是文法更加直覺，但是卻不易維護。有時候采用第一種方法是無法解決沖突的，第二種方法是唯一的選擇。

四、工作過程

javaCC在使用的時候會首先建立一個JJ檔案。這個文法檔案以一些JavaCC所提供的Options的參數設定開始。在這個例子中，Options的參數都是它們的預設值。是以，這些參數實際上是不需要的。程式員甚至可以完全忽略Options這一部分，或者省略其中的一個或多個Options的參數，詳細的關于Options的參數設定的問題請參考JavaCC的文檔。

接下來的是一個處在”PARSER_BEGIN(name)”和”PARSER_END(name)”中間的編譯單元。這個編譯單元可以是任意的複雜。在這個編譯單元中唯一的限制就是它必須定一個一個叫”name”的類——與PARSER_BEGIN和PARSER_END的參數的相同。這個”name”被用作文法分析産生器生成的java檔案的字首。

JavaCC的輸入文檔是一個詞法和文法的規範檔案，其中也包括一些動作的描述，它的字尾應該是jj。

簡而言之，一個jj文檔由下面幾個部分構成：

（1）Options{}部分：這個部分對産生的文法分析器的特性進行說明，例如向前看的token的個數（用來解除沖突）。這一部分是可以省略的，因為每一個選項都有預設值，當我們沒有對某個選項進行說明時，它就采用預設值。也可以把這些選項作為javacc指令的參數來啟動javacc，可以達到同樣的效果。

（2）分析器類的聲明：這個部分指定了分析器類的名字，以及其他類中成員的聲明。這個部分是必須有的。這個部分的聲明如下：

PARSER_BEGIN(classname)

Class classname {

……

}

PARSER_END(classname)

（3）詞法部分聲明：這裡面有四類：SKIP、TOKEN、SPECIAL_TOKEN、MORE。其中，SKIP用來說明被忽略的串，下面是一個例子：

SKIP {

“ “

|

“\n”

|

“\r”

}

TOKEN用來說明在詞法層次上識别的token，下面是一個例子：

TOKEN {

/**
 * the javacc file of CMM
 * By huxijie 2014302580184
 */
options
{
  static = true;
}
PARSER_BEGIN(cmm)
package experiment1;
public class cmm
{
  public static void main(String args []) throws ParseException
  {
    cmm parser = new cmm(System.in);
    while (true)
    {
      System.out.println("------從标準輸入中讀取-------");
      System.out.println("請輸入一個CMM程式進行分析（最後輸入“$表示開始分析”）或者輸入#退出:");
      try
      {
        switch (cmm.one_line())
        {
          case  : 
          System.out.println("成功!.");
          break;
          case  : 
          System.out.println("再見!");
          break;
          default : 
          break;
        }
      }
      catch (Exception e)
      {
        System.out.println("失敗!.");
        System.out.println(e.getMessage());
        cmm.ReInit(System.in);
      }
      catch (Error e)
      {
        System.out.println("錯誤!.");
        System.out.println(e.getMessage());
        break;
      }
    }
  }
}
PARSER_END(cmm)
SKIP :  /*跳過*/
{
  " "
| "\r"
| "\t"
| "\n"
| "\r\n"
| < "//" (~[ "\n", "\r" ])*
    (
      "\n"
    | "\r"
    | "\r\n"
    ) >
| < "/*" (~[ "*" ])* "*"
    (
      ~[ "/" ] (~[ "*" ])* "*"
    )*
    "/" >
}
TOKEN : /*定義操作符*/
{
  < PLUS : "+" >
| < MINUS : "-" >
| < MULTIPLY : "*" >
| < DIVIDE : "/" >
| < ASSIGN : "=" >
}
TOKEN : /*定義關系符*/
{
  < LT : "<" >
| < GT : " >" >
| < LEQ : "<=" >
| < GEQ : ">=" >
| < EQ : "==" >
| < NEQ : "<>" >
}
TOKEN : /*定義括号*/
{
  < LPARENTHESES : "(" >
| < RPARENTHESES : ")" >
| < LBRACE : "{" >
| < RBRACE : "}" >
| < LBRACKET : "[" >
| < RBRACKET : "]" >
}
TOKEN : /*定義保留字*/
{
  < IF : "if" >
| < ELSE : "else" >
| < WHILE : "while" >
| < READ : "read" >
| < WRITE : "write" >
| < INT : "int" >
| < REAL : "real" >
}
TOKEN : /*定義其他符号*/
{
  < COMMA : "," >
| < SEMICOLON : ";" >
| < COLON : ":" >
| < UNDERLINE : "_" >
}
TOKEN :  /*定義整數和實數*/
{
  < POSITIVEINT : [ "1"-"9" ] (< DIGIT >)* >
| < REALNUMBER :
    (
      (< DIGIT >)+ "." (< DIGIT >)+
    )
  | "0." (< DIGIT >)+ >
  //| < CONSTANT : (["0"] | ["1"-"9"](<DIGIT>)*) | (<INTEGER>"."(<DIGIT>)+) >
| < #DIGIT : [ "0"-"9" ] >
| < #DIGIT_0 : [ "1"-"9" ] >
}
TOKEN : /*定義辨別符*/
{
  < IDENTIFIER :
    [ "a"-"z", "A"-"Z" ]
    (
      ([ "a"-"z", "A"-"Z", "_", "0"-"9" ])* ([ "a"-"z", "A"-"Z", "0"-"9" ])
    )? >
}
int one_line() :
{}
{
  procedure()"$"
  {
    return ;
  }
| "#"
  {
    return ;
  }
}
void sum() :     /*算術表達式*/
{}
{
  term()
  (
    (
      < PLUS >
    | < MINUS >
    )
    term()
  )*
}
void term() :    /*項*/
{}
{
  unary()
  (
    (
      < MULTIPLY >
    | < DIVIDE >
    )
    unary()
  )*
}
void unary() :  /*一進制式*/
{}
{
  < MINUS > element()
| element()
}
void element() :    /*元素*/
{}
{
  (
    < POSITIVEINT >
  | < REALNUMBER >
  )
| < IDENTIFIER > (< LBRACKET > < POSITIVEINT > < RBRACKET >)?
| < LPARENTHESES > sum() < RPARENTHESES >
}
void relational() :  /*關系表達式*/
{
}
{
  (
    < IDENTIFIER >
  | sum()
  )
  (
    (
      < LT >
    | < GT >
    | < LEQ >
    | < GEQ >
    | < EQ >
    | < NEQ >
    )
    (
      < IDENTIFIER >
    | sum()
    )
  )+
}
void declaration() :    /*聲明語句*/
{}
{
  (
    < INT >
  | < REAL >
  )
  < IDENTIFIER >
  (
    < LBRACKET > (< POSITIVEINT >)? < RBRACKET >
    (
      < ASSIGN > < LBRACE >
      (
        sum()
        (
          < COMMA > sum()
        )*
      )?
      < RBRACE >
    )?
    (
      < COMMA > < IDENTIFIER >
      (
        (
          < LBRACKET > (< POSITIVEINT >)? < RBRACKET >
          (
            < ASSIGN > < LBRACE >
            (
              sum()
              (
                < COMMA > sum()
              )*
            )?
            < RBRACE >
          )?
        )
      |
        (
          < ASSIGN > sum()
        )?
      )
    )*
    < SEMICOLON >
  |
    (
      < ASSIGN > sum()
    )?
    (
      < COMMA > < IDENTIFIER >
      (
        (
          < LBRACKET > (< POSITIVEINT >)? < RBRACKET >
          (
            < ASSIGN > < LBRACE >
            (
              sum()
              (
                < COMMA > sum()
              )*
            )?
            < RBRACE >
          )?
        )
      |
        (
          < ASSIGN > sum()
        )?
      )
    )*
    < SEMICOLON >
  )
}
void assignment() : /*指派語句*/
{}
{
  < IDENTIFIER >
  (
    < LBRACKET > < POSITIVEINT > < RBRACKET > < ASSIGN > sum()
    (
      < COMMA > < IDENTIFIER >
      (
        (
          < LBRACKET > < POSITIVEINT > < RBRACKET > < ASSIGN > sum()
        )
      |
        (
          < ASSIGN > sum()
        )
      )
    )*
    < SEMICOLON >
  | < ASSIGN > sum()
    (
      < COMMA > < IDENTIFIER >
      (
        (
          < LBRACKET > < POSITIVEINT > < RBRACKET > < ASSIGN > sum()
        )
      |
        (
          < ASSIGN > sum()
        )
      )
    )*
    < SEMICOLON >
  )
}
void read() :   /*read語句*/
{}
{
  < READ > < LPARENTHESES > < IDENTIFIER >
  (
    < LBRACKET >
    (
      < POSITIVEINT >
    | < IDENTIFIER >
    )
    < RBRACKET >
  )?
  < RPARENTHESES > < SEMICOLON >
}
void write() :  /*write語句*/
{}
{
  < WRITE > < LPARENTHESES >
  (
    < IDENTIFIER >
  | sum()
  )
  < RPARENTHESES > < SEMICOLON >
}
void conditionStatement() :  /*if-else語句*/
{}
{
  < IF > < LPARENTHESES > relational() < RPARENTHESES >
  (
    (
      < LBRACE >
      (
        statement()
      )*
      < RBRACE >
    )
  | statement()
  )
  (
    < ELSE >
    (
      (
        < LBRACE >
        (
          statement()
        )*
        < RBRACE >
      )
    | statement()
    )
  )?
}
void whileStatement() :  /*while語句*/
{}
{
  < WHILE > < LPARENTHESES > relational() < RPARENTHESES >
  (
    (
      < LBRACE >
      (
        statement()
      )*
      < RBRACE >
    )
  | statement()
  )
}
void statement() :  /*語句*/
{}
{
  < SEMICOLON >
| declaration()
| assignment()
  //| relational() <SEMICOLON> 
| sum() < SEMICOLON >
| read()
| write()
| conditionStatement()
| whileStatement()
}
void procedure() :  /*程式*/
{}
{
  < SEMICOLON >
| declaration()
| assignment()
| read()
| write()
| < LBRACE >
  (
    statement()
  )*
  < RBRACE >
}