text: ## <center>**Lab1-2-左递归**</center>
  
  ## pb15111604 金泽文
  
  
  
  **测试说明**
  
  ​	在lab-1-2-answer/中分别执行一下指令
  
  ```
  sh plus.sh
  sh mult.sh
  sh unsupport.sh
  ```
  
  ​	*plus.sh 用于测试 PlusFirst.g4*
  
  ```
  root@ubuntu:/home/test/PB15111604/lab-1-2-answer# sh plus.sh
  alias antlr4=java org.antlr.v4.Tool
  antlr4 -Dlanguage=Python3 PlusFirst.g4
  python3 plus_calculator.py
  
  Please enter a expression: 1+5*6
  (1+5)
  (6*6)
  36
  ```
  
  ​	*mult.sh 用于测试 MultFirst.g4*
  
  ```
  root@ubuntu:/home/test/PB15111604/lab-1-2-answer# sh mult.sh
  alias antlr4=java org.antlr.v4.Tool
  antlr4 -Dlanguage=Python3 MultFirst.g4
  python3 mult_calculator.py
  
  Please enter a expression: 1+5*6 
  (5*6)
  (1+30)
  31
  ```
  
  ​	*unsupport.sh 用于测试不支持的左递归类型。*
  
  ```
  root@ubuntu:/home/test/PB15111604/lab-1-2-answer# sh unsupport.sh
  alias antlr4=java org.antlr.v4.Tool
  antlr4 -Dlanguage=Python3 UnsupportedLeftRecursive.g4
  
  error(119): UnsupportedLeftRecursive.g4::: The following sets of rules are mutually left-recursive [s, a] and [m] and [n] and [o] and [p] and [q] and [r]
  ```
  
  
  
  **优先级**
  
  而对于antrl4对于优先级的处理，比如：
  
  - `e : e '*' e # Mult | e '+' e # Add | INT # Int ;`
  
  - `e : e '+' e # Add | e '*' e # Mult | INT # Int ;`
  
    经过我的检验，发现左边的优先级更高，也就是说在一个|产生式中优先按照左边递推。​
  
  
  
  关于左递归的思考**
  
  ​	刚开始进行测试，将C1Parser.g4 的compilationUnit部分改为：
  
  ```
  compilationUnit: compilationUnit?  (decl | funcdef) EOF
  ```
  
  ​	结果：
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ antlr4 *.g4
  error(119): C1Parser.g4::: The following sets of rules are mutually left-recursive [compilationUnit]
  ```
  
  ​	提示为左递归错误。
  
  ​	可能是因为antlr4对支持的左递归的类型也有限制。
  
  ​	而我单独设置一个简单的SupportedLeftRecursive.g4如下：
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ cat -n SupportedLeftRecursive.g4 
       1	parser grammar SupportedLeftRecursive;
       2	options { tokenVocab = C1Lexer;  }
       3	
       4	a: a s | s;
       5	s: Number;
  ```
  
  ​	结果:
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ antlr4 SupportedLeftRecursive.g4 
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ 
  ```
  
  ​	没有报错。说明**`对于最基本的直接左递归，antlr4是支持的`**。
  
  ​	而对于
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ cat -n pportedLeftRecursive1.g4 
       1	parser grammar SupportedLeftRecursive1;
       2	options { tokenVocab = C1Lexer;  }
       3	
       4	a: a? s;
       5	s: Number;
  ```
  
  ​	结果：
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ antlr4 UnsupportedLeftRecursive1.g4 
  error(119): UnsupportedLeftRecursive1.g4::: The following sets of rules are mutually left-recursive [a]
  ```
  
  ​	提示为左递归错误。而这里的语言语上一个直接左递归的例子相同，只不过形式不同，这里用了？，结果却报错了。
  
  ​	类似的，想到 * + 等符号，果然都报错了。
  
  ​	继续想到的一个间接左递归的例子：
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ cat -n UnsupportedLeftRecursive2.g4 
       1	parser grammar UnsupportedLeftRecursive2;
       2	options {tokenVocab = C1Lexer; }
       3	
       4	s: a s | Number;
       5	a: s a | Int;
  ```
  
  ​	结果:
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ antlr4 UnsupportedLeftRecursive2.g4 
  error(119): UnsupportedLeftRecursive2.g4::: The following sets of rules are mutually left-recursive [s, a] 0
  ```
  
  ​	提示为左递归错误。
  
  ​	最后将以上归结到一个文件UnsupportedLeftRecursive.g4中。
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ cat  UnsupportedLeftRecursive.g4 
  parser grammar UnsupportedLeftRecursive;
  options {tokenVocab = C1Lexer; }
  
  s: a s | Number;
  a: s a | Int;
  
  m: m? b;
  b: Number;
  
  n: n* b;
  
  o: o+ b;
  
  p: p?? b;
  
  q: q*? b;
  
  r: r+? b;
  ```
  
  ​	结果：
  
  ```
  reaper@ubuntu:/home/PB15111604/c1recognizer/grammar$ antlr4 UnsupportedLeftRecursive.g4 
  error(119): UnsupportedLeftRecursive.g4::: The following sets of rules are mutually left-recursive [s, a] and [m] and [n] and [o] and [p] and [q] and [r]
  ```
  
  ​	综上，antlr4支持的左递归只有形如 
  
  ```
  a: a s| s;
  s: Number
  ```
  
  ​	这样的**`最直接的左递归`**。
  
  ​	而**不支持间接左递归，以及“较为复杂”的、类似直接左递归而实际上需要转化为间接左递归的左递归**。后者的例子如：
  
  ```
  m: m? b;
  b: Number;
  
  n: n* b;
  
  o: o+ b;
  
  p: p?? b;
  
  q: q*? b;
  
  r: r+? b;
  ```
  
  ​	等。
  
  ​	对于此，我的分析是：
  
  ​	以 m: m? b; 为例，antlr4会将?类似展开为
  
  ```
  m: m’ b;
  m’: m | /* epsilon */ ;
  ```
  
  ​	即在内部展开成了间接左递归，而间接左递归是不能被antlr4实现的。	
  
  ​	* 、+  的情况类似。
  
  ​	而至于antlr4间接左递归还未实现的原因，我分析认为可能是因为
  
  ```
  直接左递归可以通过循环进行左递归预测，及时剪枝。而间接左递归由于逻辑复杂，很难做到直接左递归那样。
  同时，间接左递归一般可以转化成直接左递归。
  最后，直接左递归也是antlr4中新增加的特性，也许未来能加入间接左递归也不可知。
  ```
  
  
  
  **`以上是未经调研得到的自己思考的过程，下面是调研之后所得。`**
  
  ​	经过调研验证，antlr4实现直接左递归的支持，确实是通过将左递归替换为一个判定循环(predicated loop)实现的。
  
  ​	并且经过调研发现，antlr4支持的直接左递归种类有限制。
  
  ​	首先，antlr4采用的是ALL(*)，A指Adaptive，是由ll( * ) 改进的算法。
  
  ​	**`ALL(*)在碰到多个可选分支的时候，为每个分支运行一个子parser，每个子parser有自己的dfa，以伪并行的方式探索所有可能的路径，一旦某个子parser完成匹配，则选定并终止其他parser。`**
  
  ​	显然，这个生成子parser再并行探索的过程将消耗大量的计算量，出于实际考量，antlr4只支持4中直接左递归：
  
  ```
  · 二元，如expr op expr或expr (op1 | op2 | ... | opN) expr。
  · 三元，如expr '?' expr ':' expr
  · 一元前缀，即把任意元素的尾递归视做一元前缀，如'(' type ')' expr或('+' | '-' | '++' | '--') expr
  · 一元后缀，如expr '.' identifier
  ```
  
  ​	这样，间接左递归并不被支持也可以理解。因为复杂的产生式将产生巨大的计算量，而对于文法来说，间接左递归一般手工转化为直接左递归，而直接左递归又以以上三种为主，这样既能涵盖绝大部分的需求，又能保证计算量不爆炸，赞！
  
  
  
  以上，就是我对于antlr4左递归的思考、分析、与调研。
  
  
  
  **`说明`**：以上的中间程序是我思考的过程测试用的，并没有提交到git库中，而是将最后的结果总结到了要提交的g4中。
  