Lex & Yacc - Rexical & Racc

January 27, 2019 00:59


Lex

一个词法分析程序。通过定义好的规则,生成对应的 C/C++ 分析代码。

一个 Lex 文件分为三部分,使用 %% 分隔

{ 定义 }
%%
{ 规则 }
%%
{ 用户代码 }

Lex 定义 都是以 % 打头的,以 %{ %} 定义的内容会直接 copy 到生成的 C/C++ 代码中。 最后一个 %% 后的 用户代码 也会直接复制到生成的代码中。

先来个简单的字符统计 counter.lex

%{
  int chars = 0;
  int words = 0;
  int lines = 0;
%}

%%
[a-zA-Z]+ { words++; chars = chars + strlen(yytext); }
\n chars++; lines++;
. chars++;
%%

int main(int argc, char **argv) {
  yylex();
  printf("Lines: %d  Words: %d  Chars: %d\n", lines, words, chars);

  return 0;
}

上面代码第一块定义中,我们先定义了三个用来统计的全局变量。

第二块的规则中,左侧为 Lex 正则表达式,右侧为需要执行的代码, 上面规则中,我们分别匹配不同的字符并增加不同的计数器。

第三块的代码中,加入了 main 函数,调用 yylex() 执行分析程序,并打印出结果。

编译运行

lex -o counter.yy.c counter.lex
cc counter.yy.c -o main -ll
cat | ./main
Hello world!
What is your name?
^D

将会输出

Lines: 2  Words: 6  Chars: 32

更多内容请参考 Lex 文档

Yacc

想要分析结构化的文本,单单靠 Lex 是很难做到的。Yacc 可以通过语法级的规则来生成更复杂的分析器。

Yacc 文件结构和 Lex 一样

声明、定义
%%
规则
%%
用户代码

规则结构为 name: body;

还是先看代码,下面是一个计算器的代码。

parser.y 文件

/*
  定义将要使用的 token,Lex 将匹配到的内容标识为对应的 token,
  语法规则中可以直接使用这些 token 来指代 Lex 匹配到的内容。
  这里定义的都是一个计算器要用的变量,值,加减乘除之类的符号及操作
*/
%token VAR VAL COUNT RESULT EQ ADD ADD_EQ DEC DEC_EQ MUL MUL_EQ DIV DIV_EQ POW RESET EXIT LBRACE RBRACE

/* 越后的优先级越高,没有括号的情况下,计算器要先算幂,再是乘除,最后加减 */
%left ADD DEC
%left MUL DIV
%left POW

/* 为不同规则定义不同的返回类型 */
%union {
  double val;
  int var;
}

/* 自动匹配 expr 规则及 VAL token 使用 val 变量( 也就是 double 类型 ) */
%type <val> expr VAL 
/* 自动匹配 VAR token 使用 var 变量( int 类型 ) */
%type <var> VAR

%{
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* 用来存放计算结果和变量值 */
double result = 0;
double vars[26];
%}


%%
commands: /* 第一条规则为 root 规则,规则名称可以自定,这里使用的 commands */
  /* | 竖线符号是"或"的意思。这里表示, commands 这个规则,
    要么是 commands 这个规则再带一条 cmd 规则,要么就是空的(竖线右为空)
    因为 commands 包涵了自身,所以解析时会一直递归执行,直到没有要解析的内容才结束
  */
  commands cmd |
  ;

cmd:
  /* 定义 cmd 规则,要么是 count 规则(我们用来计算表达式的),
    要么是 reset 规则(我们用来清空变量及计算结果的)
    要么就是 EXIT 这个预告定义好的 token
  */
  count
  | reset
  | EXIT { exit(0); } /* 语法匹配后 { } 中为要执行的代码 */
  ;
count:
  expr COUNT { /* 当匹配 expr + COUNT 这个组合后,我们将保存计算结果并显示, $1 就是这个语法中第一个元素 expr  */
    result = $1;
    printf("_ = %f\n", result);
  }
  | COUNT { printf("_ = %f\n", result); } /* 显示之前的结果,如果只有 COUNT 标识 */

  /* 将 expr 的结果 $3 放到变量 $1 中,并显示值 */
  | VAR EQ expr COUNT { vars[$1] = $3; printf("%c = %f\n", $1 + 'a', vars[$1]); }

  /* 一些便捷的操作,如将变量的值加上 expr 的值 */
  | VAR ADD_EQ expr COUNT { vars[$1] = vars[$1] + $3; printf("%c = %f\n", $1 + 'a', vars[$1]); }
  | VAR DEC_EQ expr COUNT { vars[$1] = vars[$1] - $3; printf("%c = %f\n", $1 + 'a', vars[$1]); }
  | VAR MUL_EQ expr COUNT { vars[$1] = vars[$1] * $3; printf("%c = %f\n", $1 + 'a', vars[$1]); }
  | VAR DIV_EQ expr COUNT { vars[$1] = vars[$1] / $3; printf("%c = %f\n", $1 + 'a', vars[$1]); }
  ;

expr: /* 前面 count 规则中用到的 expr 就是在这里定义的 */
  VAL { $$ = $1; } /* $1 是第一个元素的值,而 $$ 呢,就是这个规则的结果值 */
  | VAR { $$ = vars[$1]; }
  | RESULT { $$ = result; }
  | expr ADD expr { $$ = $1 + $3; }
  | expr DEC expr { $$ = $1 - $3; }
  | expr MUL expr { $$ = $1 * $3; }
  | expr DIV expr { $$ = $1 / $3; }
  | expr POW expr { $$ = pow($1, $3); }
  | LBRACE expr RBRACE { $$ = $2; }
  ;

reset:
  RESET {
    result = 0;
    for (int i = 0; i < 26; i++) { vars[i] = 0; }
  }
%%

int main() {
  /* 调用 yacc 的解析程序 */
  yyparse();
  return 0;
}

/* 无法解析时的错误回调 */
int yyerror(char *msg) {
  fprintf(stderr, "Error encountered: %s\n", msg);
  return 0;
}

然后我们可以编译语法定义并生成 C/C++ 代码,下面命令将会生成 y.tab.c y.tab.h

yacc -d parser.y

语法定义完了,我们继续用 Lex 做词法分析来定义 Yacc 中的 token

lang.lex

%{
/* 首先加载 yacc 为上面语法生成的头文件 */
#include "y.tab.h"

#include <stdio.h>
#include <string.h>

%}

/* 为 [a-z] 这个表达式命名为 var,之后可以直接使用 {var} 来表示这个正则 */
var [a-z]
num [0-9]
int {num}+
float {num}+[.]{num}+
ignore_str [ \t]+

%%
/* 这里的 yylval.var 就是在 parser.y 中定义的 union 中的 var
  a-z 的变量,在 yacc 中我们存放在一个长度为 26 的数组中
  yytext 为当前表达式匹配到的文本
  就一句就是将匹配到的内容存放到 yylval 变量中,并告诉 parser.y 这是一个 VAR (预先定义好的 token)
*/
{var} { yylval.var = *yytext - 'a'; return VAR; }

({int}|{float}) { yylval.val = atof(yytext); return VAL; };
\n { return COUNT; };  /* 将换行定义为计算结果 COUNT token */
_ { return RESULT; };
= { return EQ; };
\+ { return ADD; };
\+= { return ADD_EQ; };
\- { return DEC; };
\-= { return DEC_EQ; };
\* { return MUL; };
\*= { return MUL_EQ; };
\*\* { return POW; };
\/ { return DIV; };
\/= { return DIV_EQ; };
\( { return LBRACE; }
\) { return RBRACE; }
reset { return RESET; }
exit|quit { return EXIT; }
{ignore_str} /* 表达式右侧无内容表示将忽略这些字符,这里我们将忽略空格及 tab */
%%

/* 在文件或输入的末尾将会被调用,返回 1 表示结束解析 */
int yywrap() {
  return 1;
}

下面我们编译并执行我们的计算器程序

lex lang.lex
cc lex.yy.c y.tab.c -o main -ll
cat | ./main
1 + 2 * 3 + 4
1 + 2 * (3 + 4)
(1 + 2) * 3 + 4
(1 + 2) * (3 + 4)
_ * 1
a = _
b = 123
c = a * b
_ * _
n = 1 + 2 ** 3
n / 3
n += 3
n -= 1
n *= 3
n /= 2
^D

将会输出

_ = 11.000000
_ = 15.000000
_ = 13.000000
_ = 21.000000
_ = 21.000000
a = 21.000000
b = 123.000000
c = 2583.000000
_ = 441.000000
n = 9.000000
_ = 3.000000
n = 12.000000
n = 11.000000
n = 33.000000
n = 16.500000

更多内容可以参考 Yacc 手册

Rexical & Racc

在 Ruby 里面怎么玩 Lex & Yacc 这套呢?那就是 Rexical & Racc 了,规则语法基本都差不多

功能方面,Rexical 相对 Lex 要弱不少。 而 Racc 大概和 Yacc 一样强大了,语法也差不多

Yacc 的 $$ 变成了 result, $1 $2 语法元素全都放到一个 val 变量中了

那么我们同样是写一个计算器,这次使用 Rexical 与 Racc

先上 Rexical 文件 cal.rex


class Calculator
macro
  var [a-z]+[a-z0-9_]*
  num [0-9]
  int {num}+
  float {num}+[.]{num}+
  ignore_str [\ \t]+

rule
  reset { [:RESET, nil] }
  exit|quit { [:EXIT, nil] }
  {var} { [:VAR, text] }
  ({int}|{float}) { [:VAL, text.to_f] }
  \n { [:COUNT, nil]  }
  _ { [:RESULT, nil] }
  = { [:EQ, nil] }
  \+= { [:ADD_EQ, nil] }
  \+ { [:ADD, nil] }
  \-= { [:DEC_EQ, nil] }
  \- { [:DEC, nil] }
  \*= { [:MUL_EQ, nil] }
  \*\* { [:POW, nil] }
  \* { [:MUL, nil] }
  \/= { [:DIV_EQ, nil] }
  \/ { [:DIV, nil] }
  \( { [:LBRACE, nil] }
  \) { [:RBRACE, nil] }
  {ignore_str}
end

这个匹配按从上到下的顺序来的,如果 +=+ 下面的话,就永远匹配不到 +=。 看了下 Rexical 的实现代码,也就简单的使用 String#scan 方法

编译这个规则文件到 ruby 文件,会在 scan_strscan_file 两个方法中调用 Racc 的 do_parse 而且为 Calculator 类定义好了 next_token 方法

rex cal.rex -o lexer.rb

再是 Racc 的 cal.y, 只要对接上 next_token 方法就好了。当调用 do_parse 方法后,会一直调用 next_token 直到返回空。next_token 的返回值为 [:SYMBOL, val], rule 中可以直接使用 SYMBOL 匹配到 next_token 第一个值对应的名字

class Calculator

prechigh
  left MUL DIV
  left ADD DEC
  right EQ ADD_EQ DEC_EQ MUL_EQ DIV_EQ
preclow

rule
  cmd: 
    count | reset | EXIT { exit }

  count:
    expr COUNT { @result = val[0]; puts "_ = #{@result}" }
    | COUNT { puts "_ = #{@result}" }
    | VAR EQ expr COUNT     { v0, v2 = val[0], val[2]; @vars[v0] = v2; puts "#{v0} = #{@vars[v0]}" }
    | VAR ADD_EQ expr COUNT { v0, v2 = val[0], val[2]; @vars[v0] += v2; puts "#{v0} = #{@vars[v0]}" }
    | VAR DEC_EQ expr COUNT { v0, v2 = val[0], val[2]; @vars[v0] -= v2; puts "#{v0} = #{@vars[v0]}" }
    | VAR MUL_EQ expr COUNT { v0, v2 = val[0], val[2]; @vars[v0] *= v2; puts "#{v0} = #{@vars[v0]}" }
    | VAR DIV_EQ expr COUNT { v0, v2 = val[0], val[2]; @vars[v0] /= v2; puts "#{v0} = #{@vars[v0]}" }

  expr:
    VAL { result = val[0] }
    | VAR { result = @vars[val[0]] }
    | RESULT { result = @result }
    | expr ADD expr { result = val[0] + val[2] }
    | expr DEC expr { result = val[0] - val[2] }
    | expr MUL expr { result = val[0] * val[2] }
    | expr DIV expr { result = val[0] / val[2] }
    | expr POW expr { result = val[0] ** val[2] }
    | LBRACE expr RBRACE { result = val[1] }

  reset:
    RESET { @result = 0; @vars.clear }
end

# ---- header 标识下的内容将会生成到文件头
---- header
require './lexer'

# ---- inner 标识下的内容将会生成到 Calculator 类中成为实例方法
---- inner

def run
  @result = 0
  @vars = {}
  while str = gets do scan_str(str) end
end

# ---- footer 标识下的内容将会生成到文件末尾
---- footer
Calculator.new.run

Racc 和 Yacc 还是比较像的,没啥可说的。编译运行

racc cal.y
cat | ruby cal.tab.y
1 + 2 * 3 + 4
1 + 2 * (3 + 4)
(1 + 2) * 3 + 4
(1 + 2) * (3 + 4)
_ * 1
a = _
b = 123
c = a * b
_ * _
n = 1 + 2 ** 3
n / 3
n += 3
n -= 1
n *= 3
n /= 2
^D

输入结果

_ = 11.0
_ = 15.0
_ = 13.0
_ = 21.0
_ = 21.0
a = 21.0
b = 123.0
c = 2583.0
_ = 441.0
n = 9.0
_ = 3.0
n = 12.0
n = 11.0
n = 33.0
n = 16.5

更多 Racc 语法参考这里

END

本来想再写写生成 LLVM AST 再编译的, 但是 Ruby 的 llvm binding ruby-llvm 对应的版本过老,而且还有一些 Bug。Example 都运行不起来了。实在是折腾不起来啊。而 C/C++ 版本的话。代码写的实在是太罗嗦了,懒的去折腾了。

先就这样了,以后有机会再折腾。

Comments: