saenai no heroine

读书笔记 - 自制编译器

读书笔记
字数统计: 1,181阅读时长: 5 min
2020/05/09 Share

第1部分

第三章 语法分析的概要

3.3 JavaCC 的概要

语法描述文件的例子

代码清单 3.1 Adder.jj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
options {
	STATIC = false;
}

PARSER_BEGIN(Adder)
...
PARSER_END(Adder)
SKIP: { <[" ","\t","\r","\n"]> }
TOKEN: {
	<INTEGER: (["0"-"9"])+>
}
long expr():
{
	Token x, y;
}
{
	x=<INTEGER> "+" y=<INTEGER> <EOF>
		{
			return Long.parseLong(x.image) + Long.parseLong(y.image);
		}
}

之后的 SKIP 和 TOKEN 部分定义了扫描器。SKIP 表示要跳过空格、制表符（tab）和换行 符。TOKEN 表示扫描整数字符并生成 token。
从 long expr... 开始到最后的部分定义了狭义的解析器。这部分解析 token 序列并执行 某些操作。cbc 生成抽象语法树， 但 Adder 类并不生成抽象语法树， 而是直接计算表达式的 结果。

读到这里的时候突然想到一个问题，SKIP 和 TOKEN 部分定义的扫描器中并没有关于 "+" 的定义，而这个符号出现在定义解析器的规则中，那么使用这样定义扫描器加解析器的组合是否能够正确分析 1+2 这样的输入呢？
按照一般的想法来说，"+" 并没有在扫描器的定义中出现，那么根据上述定义生成的扫描器理应无法识别输入中出现的 "+" 符号，但是在实际的测试中却能够成功的识别，所以猜测在解析器定义的规则中出现的 "+" 实际上在生成扫描器时也会被当作作为 TOKEN 定义的一部分，所以最后生成的扫描器能够正确识别输入中的 "+" 符号， ["0"-"9"] 以及 [" ","\t","\r","\n"] 。

相关的定义在 JavaCC 的文档中有提到：

JavaCC - Grammar - Production
JavaCC - regular_expr_production
JavaCC - regexpr_spec
JavaCC - regular_expression
JavaCC - expansion_unit

Grammar

Production
1
2
3
4
production ::= javacode_production
             | regular_expr_production
             | bnf_production
             | token_manager_decls

There are four kinds of productions in JavaCC.

-  [javacode_production](https://javacc.github.io/javacc/documentation/grammar.html#javacode-production)  and  [bnf_production](https://javacc.github.io/javacc/documentation/grammar.html#bnf-production)  are used to define the grammar from which the parser is generated.
-  [regular_expr_production](https://javacc.github.io/javacc/documentation/grammar.html#regular-expr-production)  is used to **define** the **grammar** **tokens** - the token manager is generated from this information (as well as from **inline token specifications in the parser grammar**).
-  [token_manager_decls](https://javacc.github.io/javacc/documentation/grammar.html#token-manager-decls)  is used to introduce declarations that get inserted into the generated token manager.
regular-expression
1
2
3
4
regular_expression ::= java_string_literal
                     | "<" [ [ "#" ] java_identifier ":" ] complex_regular_expression_choices ">"
                     | "<" java_identifier ">"
                     | "<" "EOF" ">"

There are two places in a grammar files where regular expressions may be written:

1. Within a  [regular expression specification](https://javacc.github.io/javacc/documentation/grammar.html#regexpr_spec)  (part of a  [regular expression production](https://javacc.github.io/javacc/documentation/grammar.html#regular-expr-production) ),
2. As an  [expansion unit](https://javacc.github.io/javacc/documentation/grammar.html#expansion-unit)  with an  [expansion](https://javacc.github.io/javacc/documentation/grammar.html#expansion) . When a regular expression is used in this manner, it is as if the regular expression were defined in the following manner at this location and then referred to by its label from the expansion unit:

1
2
3
4
<DEFAULT> TOKEN :
{
  regular expression
}

That is, this usage of regular expression can be rewritten using the other kind of usage. The complete details of regular expression matching by the token manager is available in the token manager tutorial . The description of the syntactic constructs follows.

expansion_unit

…
An expansion unit can be a regular expression . Then a legal parse of the expansion unit is any token that matches this regular expression. When a regular expression is matched, it creates an object of type Token. This object can be accessed by assigning it to a variable by prefixing the regular expression with variable =. In general, you may have any valid Java assignment left-hand side to the left of the =. This assignment is not performed during lookahead evaluation.
…

第5章 基于 JavaCC 的解析器的描述

5.1 基于 EBNF 语法的描述

终端符和非终端符

这里请记住 1 个术语。JavaCC 中将刚才的“语句”“函数调用”“表达式”等非 token 的语法单位称为非终端符（nonterminal symbol），并将非终端符像 Java 的函数调用一样在后面加上 括号写成 stmt() 或 expr()。
既然有“非”终端符，自然也有终端符。终端符（terminal symbol）可以归纳为 token。使用在扫描器中定义的名称， 可以写成 或 。 并且 JavaCC 中除了扫描器中定义的 token 以外， “ =” 、” +” 、” ==” 这样的字符串字面量也可以作为终端符来使用。

一开始看到这里就产生了之前的疑问，因为终端符除了包含在扫描器中定义的 token 外，还包括字符串字面量，那么如果这些字符串字面量没有在扫描器中的 token 被定义的话，那么它们是否能够被这样定义的扫描器加解析器的组合识别并生成相应的 token ？
根据我一开始的理解，扫描器只能识别在扫描器相应定义中被定义的 token ，但是后来查阅 JavaCC 的文档发现，token 除了能在扫描器的定义中被定义以外，还能在分析器的定义中定义，比如上面提到的字符串字面量。

CATALOG
  1. 1. 第1部分
    1. 1.1. 第三章 语法分析的概要
      1. 1.1.1. 3.3 JavaCC 的概要
        1. 1.1.1.1. 语法描述文件的例子
        2. 1.1.1.2. Grammar
          1. 1.1.1.2.1. Production
          2. 1.1.1.2.2. regular-expression
          3. 1.1.1.2.3. expansion_unit
    2. 1.2. 第5章 基于 JavaCC 的解析器的描述
      1. 1.2.1. 5.1 基于 EBNF 语法的描述
        1. 1.2.1.1. 终端符和非终端符
Total : 8
2020
2019
Invalid date
2019
2018
C++ dynamic programming 读书笔记