I. Overview

Input:

• Charater stream $s$
• (implicit) Token specification

Output:

• Token stream

<aside> 💡 三种设计方法

1. 词法分析器生成器 (e.g. ANTLR)

   $\tt spec. ⇒ ANTLR ⇒ lexer$

2. 手写词法分析器

3. 自动化词法分析器

   Write an ANTLR-like generator on your own

GCC 仍旧使用手写词法分析器，效率更高，且复杂度可控

</aside>

II. ANTLR

antlr4/index.md at master · antlr/antlr4

I/O

• 输入: 词法单元的规约

  $\texttt{antlr4 SimpleExpr.g4}$

• 输出: 词法分析器

  $\texttt{SimpleExpr.tokens + SimpleExprLexer.java}$

Grammar

antlr4/lexicon.md at master · antlr/antlr4

antlr4/grammars.md at master · antlr/antlr4

• 最高层语法结构 $\texttt{prog ::= \{<stat>...\}; [EOF]}$

  • 语法规则名小写字母开头
  • $\tt EOF$: 全部输入读完才可以接收

• 语句 $\texttt{stat ::= \{<expr>|<ID>|<token>\}...}$

• 表达式 $\texttt{expr ::= \{<expr>|<ID>|<token>\}...}$

  • 顺序表明 precedence ⇒ 保证 unambiguity 的重要方法

• 词法单元 $\texttt{ID ::= \{<fragment>|<token>\}...}$

  • (terminals?) 通常全部大写 e.g. $\texttt{ID, INT, LETTER}$
  • token 字符串是 implicit 词法单元，在 ANTLR 处理时会生成临时 ID
  • $\tt fragment$ identifier: rules that are not tokens but rather aid in the recognition of tokens e.g. $\gdef\gr{\textcolor{green}} \gdef\dr{\textcolor{darkred}} \gdef\dg{\textcolor{darkgreen}} \gdef\db{\textcolor{blue}} \gdef\or{\textcolor{orange}}

  \texttt{\db{fragment} LETTER}$

  • WS: [ \\t\\r\\n]+ -> skip 跳过空白符
  • Non-greedy: .*?

<aside> 💡 ANTLR v4 中两大冲突解决规则

• 最前优先匹配: 关键字 vs. 标识符
• 最长优先匹配: >=, ifhappy, thenext, 1.23 </aside>

III. 词法单元的归约 Regular Expression