1. 奇怪的发现

• 在学习使用Antlr4的Visitor模式实现一个简单的整数计算器时，笔者使用语法规则stat对输入字符流进行语法分析

• 输入的字符流，实际上对应多个stat的rule element，而stat一次只能匹配一个，剩余的语句将被忽略

  String input = "1 + 2 * 3\n" // PrintEXpr，只有该语句被识别+ "b = (5 - 2) / 2\n" // Assgin+ "c = a + b\n" // Assgin+ "c\n"; // PrintEXpr
  

• 笔者想打印lexer识别出来的token，看截断发生在词法分析，还是语法分析阶段

• 因此，修改main()方法如下：

  CommonTokenStream tokenStream = new CommonTokenStream(lexer);
  // 新增代码，打印token
  for (Token token : tokenStream.getTokens()) {System.out.println(token);
  }
  

• 却发现执行结果与先前无异，根本没有token信息。

• debug跟踪后发现，此时的tokens竟然不包含任何的token
  

2. parser触发词法分析

• 网上查阅资料后，在StackOverflow上发现一个相同的问题：ANTLR4 Lexer getTokens() returning 0 tokens

• 有一个回答，得到了认可：

  Normally, the Parser is responsible for initiating the lexing of the input stream. To initiate lexing manually, call CommonTokenStream.fill() (which is implemented in BufferedTokenStream).

• 从第一句话可知：对输入字符流的词法分析，是有parser负责触发的

• 修改main()方法如下，对其进行验证：

  ParseTree stat = parser.stat();
  // 新增代码移到此处
  for (Token token : tokenStream.getTokens()) {System.out.println(token);
  }
  

• 此时，可以成功打印出token
  

3. 不懂就问

问题一：为什么是parser触发词法分析？

• 笔者愚见：懒加载的思想，需要使用token时，才对tokenSource（即输入字符流）进行词法分析
• CommonTokenStream继承BufferedTokenStream，BufferedTokenStream的类注释上也有类似描述：

  This implementation of TokenStream loads tokens from a TokenSource on-demand, and places the tokens in a buffer to provide access to any previous token by index.

• 语法分析以tokens作为输入，而此时尚未对tokenSource进行词法分析，因此需要触发词法分析
• 从源码的角度加以佐证

  • BufferedTokenStream的源码中，一个与懒加载有关的方法：

    protected final void lazyInit() {if (p == -1) {setup();}
    }protected void setup() {sync(0);p = adjustSeekIndex(0);
    }
    

  • TokenStream中，很多与识别token有关的方法，基本都会在方法开头调用lazyInit()，以避免重复进行词法分析
    

  • 由于懒加载机制，使用parser.stat()进行语法分析时，会触发词法分析
    

问题二：为什么还识别出了额外的token b？

• 从打印结果可以看出，除了1+2*3对应的token，还有一个多余的token b
• 词法分析的截断貌似没有**“想象”**的那么聪明，按理应该在token 3之后就没有了
• 笔者的猜测：
  • Antlr使用LL(*)文法，甚至从Antlr4开始更是使用Adaptive LL(*)
  • 这里实际使用了LL(1)文法，会向前看一个符号：3之后的下一个字符是\n，直接被忽略；再下一个是b，到此发现不再符合stat的语法规则，因此停止对输入字符流的词法分析
• 如果上述猜测成立的话，再大胆猜测一下：
  • 词法分析和语法分析是同时进行的，而非词法分析全部完成后，再进行语法分析
  • 这样可以及时停止词法分析，避免资源浪费，提升分析速度

问题三：CommonTokenStream.fill()是否具有截断特性？

• 修改main()方法如下，使用fill()方法手动触发词法分析，并将tokens与语法分析后的进行对比

  public static void main(String[] args) {// 多个stat，只能识别到第一个statString input = "1 + 2 * 3\n"+ "b = (5 - 2) / 2\n"+ "c = a + b\n"+ "c\n";// 词法分析，解析出tokenCharStream charStream = CharStreams.fromString(input);CalculatorLexer lexer = new CalculatorLexer(charStream);CommonTokenStream tokenStream = new CommonTokenStream(lexer);tokenStream.fill();System.out.println("语法分析前，通过tokenStream.fill()得到的tokens：");for (Token token : tokenStream.getTokens()) {System.out.println(token);}// 基于token进行语法分析，得到语法解析树CalculatorParser parser = new CalculatorParser(tokenStream);ParseTree stat = parser.stat();// 语法分析，触发了词法分析，此时打印token，token已存在System.out.println("语法分析后的tokens：");for (Token token : tokenStream.getTokens()) {System.out.println(token);}// 打印语法解析树并对其进行visit遍历System.out.printf("stat对应的语法解析树如下:\n%s\n", stat.toStringTree(parser));CalculatorBaseVisitor visitor = new CalculatorVisitorImpl();visitor.visit(stat);
  }
  

• 最终执行结果如下：

  • 可以看出fill()方法对输入字符流进行词法分析，直到字符流末尾（Get all tokens from lexer until EOF）
  • 通过fill()方法手动触发词法分析后，parser无需再触发词法分析，可以直接使用tokenStream中缓存的tokens。因此，打印出来的tokens没有变化

  语法分析前，通过tokenStream.fill()得到的tokens：
  [@0,0:0='1',<8>,1:0]
  [@1,2:2='+',<6>,1:2]
  [@2,4:4='2',<8>,1:4]
  [@3,6:6='*',<4>,1:6]
  [@4,8:8='3',<8>,1:8]
  [@5,10:10='b',<9>,2:0]
  [@6,12:12='=',<1>,2:2]
  [@7,14:14='(',<2>,2:4]
  [@8,15:15='5',<8>,2:5]
  [@9,17:17='-',<7>,2:7]
  [@10,19:19='2',<8>,2:9]
  [@11,20:20=')',<3>,2:10]
  [@12,22:22='/',<5>,2:12]
  [@13,24:24='2',<8>,2:14]
  [@14,26:26='c',<9>,3:0]
  [@15,28:28='=',<1>,3:2]
  [@16,30:30='a',<9>,3:4]
  [@17,32:32='+',<6>,3:6]
  [@18,34:34='b',<9>,3:8]
  [@19,36:36='c',<9>,4:0]
  [@20,38:37='',<-1>,5:0]
  语法分析后的tokens：
  ... # 结果省略，与上面的tokens一致，未进行截断
  stat对应的语法解析树如下:
  (stat (expr (expr 1) + (expr (expr 2) * (expr 3))))
  打印计算结果: 1+2*3 = 7
  

4. 后记

• 参考链接 (虽然没太看懂😂)：
  • LL语法分析简介
  • 语法分析 | LL(1) 分析算法
  • Verify that a grammar is LL(1)
  • What is non LL(*) about this right-recursive Antlr rule?