javacc功能一览

概览

通过本文你能获取到什么？

1.编译原理中常见的解析器LL和LR的对比;2.javacc的特征；3.如何在java ide中进行javacc的开发；4.通过演示一个javacc计算器的例子让你对javacc有更多了解（只是一个简单地演示，不涉及过多的语法说明）。

常见的解析器对比

javacc特征

•JavaCC生成自上而下的（递归下降[1]）解析器，而不是类似YACC[2]的工具生成的自下而上的解析器。尽管不允许左递归[3]，这允许使用更通用的语法。自上而下的解析器还有许多其他优点（除了更通用的语法外），例如，调试起来更容易，能够解析到语法中的任何非终结[4]符，还可以向上传递值（属性）在解析期间在解析树中向下移动。•默认情况下，JavaCC生成一个LL(1)解析器。但是，可能有一部分语法不是LL(1)。JavaCC提供了语法和语义超前功能，可以在这些点上本地解决shift-shift歧义。例如，解析器LL(k)仅在这样的点上，但仍保留LL(1)在其他地方以获得更好的性能。对于自上而下的解析器而言，Shift-reduce和reduce-reduce冲突不是问题。•JavaCC生成的解析器是100％纯Java的，因此在JavaCC上没有运行时依赖性，并且不需要在不同的计算机平台上运行就需要进行特殊的移植工作。•JavaCC的允许扩展的BNF[5]规格-诸如(A)*，(A)+等-中的词汇和语法规格。扩展的BNF在某种程度上减轻了对左递归的需求。实际上，A ::= y(x)*与相比，扩展BNF通常更容易阅读A ::= Ax|y。•词汇规范（例如正则表达式，字符串）和语法规范（BNF）都一起写在同一文件中。由于可以在语法规范中内联使用正则表达式，并且易于维护，因此它使语法更易于阅读。•JavaCC的词法分析器[6]可以处理完整的Unicode输入，词法规范也可以包含任何Unicode字符。这有助于描述语言元素，例如允许某些Unicode字符（非ASCII）但不允许其他Unicode字符的Java标识符。•JavaCC提供类似Lex[7]的词法状态和词法动作功能。在JavaCC中是优于其他工具的具体方面是它提供的概念，如一流的状态TOKEN，MORE，SKIP和状态的变化。这样可以提供更整洁的规范以及来自JavaCC的更好的错误和警告消息。•在解析过程中，在词汇规范中定义为特殊标记的标记将被忽略，但是这些标记可供工具处理。这的一个有用的应用是在评论的处理中。•词汇规范可以将标记定义为在整个词汇规范的全局级别或单个词汇规范的基础上都不区分大小写。•JavaCC带有JJTree，这是一个功能非常强大的树构建预处理器。•JavaCC还包括JJDoc，该工具可将语法文件转换为文档文件（可选地以HTML格式）。•JavaCC提供了许多选项来定制其行为以及生成的解析器的行为。此类选项的示例包括对输入流执行的Unicode处理的种类，要执行的歧义检查的令牌数等。•JavaCC错误报告是解析器生成器中最好的报告之一。JavaCC生成的解析器能够通过完整的诊断信息清楚地指出解析错误的位置。•使用选项DEBUG_PARSER，DEBUG_LOOKAHEAD和和DEBUG_TOKEN_MANAGER，用户可以深入分析解析和令牌处理步骤。•JavaCC版本包含各种示例，包括Java和HTML语法。这些示例及其文档是熟悉JavaCC的好方法。

示例

本示例识别匹配的括号，后跟零个或多个行终止符，然后是文件结尾。

此语法中的合法字符串示例如下：

{}，}}}//…等

非法字符串的示例包括：

{}{}，}{}}，{ }，{x}// ...等等

正则表达式说明：

1.[]: 内容可选2.+: 内容出现一次或者多次3.*: 内容出现0次或者多次4.?: 内容出现0次或者一次5.|: 或6.(): 优先级改变或者整体操作7.字符列表以“〜”符号为前缀表示的字符集是不在指定集中的任何UNICODE字符。8.更多详见BNF[8]说明

语法

PARSER_BEGIN(Example)

/** Simple brace matcher. */
public class Example {

  /** Main entry point. */
  public static void main(String args[]) throws ParseException {
    Example parser = new Example(System.in);
    parser.Input();
  }

}

PARSER_END(Example)

/** Root production. */
void Input() :
{}
{
  MatchedBraces() ("\n"|"\r")* <EOF>
}

/** Brace matching production. */
void MatchedBraces() :
{}
{
  "{" [ MatchedBraces() ] "}"
}

输出

$ java Example

$ java Example {x Lexical error at line 1, column 2. Encountered: "x" TokenMgrError: Lexical error at line 1, column 2. Encountered: "x" (120), after : "" at ExampleTokenManager.getNextToken(ExampleTokenManager.java:146) at Example.getToken(Example.java:140) at Example.MatchedBraces(Example.java:51) at Example.Input(Example.java:10) at Example.main(Example.java:6)

$ java Example {}} ParseException: Encountered "}" at line 1, column 3. Was expecting one of: "\n" ... "\r" ... at Example.generateParseException(Example.java:184) at Example.jj_consume_token(Example.java:126) at Example.Input(Example.java:32) at Example.main(Example.java:6)

如何在java IDE上进行javacc的开发?

这里主要介绍下在idea中的安装方式如下：

第一步，在idea上安装javacc插件

如下图所示安装javaCC插件。

第二步，引入maven插件

<plugins>
    <plugin>
        <groupId>org.codehaus.mojo</groupId>
        <artifactId>javacc-maven-plugin</artifactId>
        <version>2.4</version>
        <configuration>
            <sourceDirectory>${basedir}/src/main/test</sourceDirectory>
            <includes>
                <include>**/*.jj</include>
            </includes>
            <lookAhead>2</lookAhead>
            <isStatic>false</isStatic>
        </configuration>
    </plugin>
</plugins>

第三步，执行命令，生成代码

mvn javacc:javacc

命令执行后会在generated-sources目录下生成对应的java代码，在idea上将代码根目录设置为source目录即可正常加载。

计算器示例

Calculator.jj的详细代码如下：

PARSER_BEGIN(Calculator)
package com.test.parser.javacc.calc;

import java.io.* ;

public class Calculator {

    public Calculator(String expr) {
        this((Reader)(new StringReader(expr)));
    }

    public static void main(String[] args) throws Exception  {
       Calculator calc = new Calculator(args[0]);
       System.out.println(calc.calc());
    }
}

PARSER_END(Calculator)



// 忽律的字符
SKIP:{
    " "
    | "\t"
    | "\n"
    | "\r"
    | "\r\n"
}


// 关键字
TOKEN:{
    <ADD :"+">
    | <SUB :"-">
    | <MUL :"*">
    | <DIV :"/">
    | <NUMBER :
            <DIGITS>
            | <DIGITS> "." <DIGITS>
            | <DIGITS> "."
            | "." <DIGITS>
      >
    | <#DIGITS : (["0"-"9"])+ >
}

// 计算
double calc():
{
    Double value ;
    Double result = 0.0;
}
{
  result = term()
  // 加减
  (
      <ADD>
      value = term()
      {result += value;}
      |
      <SUB>
      value =term()
      {result -= value;}
  )*
  {return result;}
}

// 乘除
double term():
{
    double value;
    double result;
}
{
    result = getNumber()
    (
       <MUL>
        value = getNumber()
        {result *= value;}
       |
       <DIV>
       value = getNumber()
       {result /= value;}
    )*
    {return result;}

}

// 获取字符串
double getNumber():
{
    double number;
    Token t;
}
{
    t = <NUMBER>
    {number = Double.parseDouble(t.image);
    return number;}
}

生成代码结构如下图：

image-20201102163349917.png)

调用方式

在Calculator.jj上运行main方法，在Program arguments中传入1+2，即会输出结果3.0。

参考

•https://javacc.github.io/javacc/•https://techblogmu.blogspot.com/2017/12/difference-between-ll-parser-vs-lr.html•https://zh.wikipedia.org/wiki/%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F•https://mlog.club/article/1872278•https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form•https://en.wikipedia.org/wiki/Left_recursion

References

[1] 递归下降: https://en.wikipedia.org/wiki/Recursive_descent_parser [2] YACC: https://en.wikipedia.org/wiki/Yacc [3] 左递归: https://en.wikipedia.org/wiki/Left_recursion [4] 非终结: https://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols [5] 扩展的BNF: https://en.wikipedia.org/wiki/Extended_Backus–Naur_form [6] 词法分析器: https://en.wikipedia.org/wiki/Lexical_analysis [7] 类似Lex: https://en.wikipedia.org/wiki/Lex_(software) [8] BNF: https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form