AlpacaTutorial - activesys/alpaca-llama GitHub Wiki

alpaca tutorial.

alpaca是什么，为什么会有alpaca?

alpaca是alpaca-llama工具的一部分，主要应用在词法分析算法上面，将描述词法的正则表达式集转换成为相应的DFA，然后采用DOT格式输出。DOT格式是一种画图脚本，graphviz软件可以将这个脚本转换成多种图片输出。

正则表达式

alpaca接受的正则表达式是正则表达式的一个子集，其具体规则请参考alpaca正则表达式规范。

一个正则表达式

首先使用一个简单的例子来展示一下alpaca的功能。《龙书》在讲解词法分析的部分使用了一个经典的正则表达式来讲解正则表达式到NFA再到DFA再到最小化DFA的整个过程(《Compilers Principles, Techniques and Tools Second Edition》Chapter 3):

(a|b)*abb

使用下面的命令来转换这个正则表达式：

[wb@activesys sample]$ alpaca.py | dot -Tpng -osample.png
(a|b)*abb
^D

当不指定输入参数和输出参数的时候alpaca使用stdin和stdout，dot是graphviz工具集中的一个工具，上面的命令将alpaca的输出当作输入并转换成png格式的图片https://github.com/activesys/alpaca-llama/blob/v1.0/sample/sample.png

消除重复

上面使用了一个简单的例子展示了一下alpaca的功能，但是这并不意味着它只能够处理单个的正则表达式，下面我们看看它如何处理多个正则表达式，并且消除重复的：

[wb@activesys sample]$ cat multi.regex 
\d
\d
\d
\d
\d
\d
\d
[wb@activesys sample]$ alpaca.py multi.regex 
digraph G {
    graph [rankdir = LR, label = "Generated by alpaca.py 1.0\n(C) 2013 [email protected]"];
    node [shape = circle];
    start [shape = plaintext, label = ""];
    start -> S0 [label = "start"];
    S1 [shape = doublecircle];
    S0 -> S1 [label = "1"];
    S0 -> S1 [label = "0"];
    S0 -> S1 [label = "3"];
    S0 -> S1 [label = "2"];
    S0 -> S1 [label = "5"];
    S0 -> S1 [label = "4"];
    S0 -> S1 [label = "7"];
    S0 -> S1 [label = "6"];
    S0 -> S1 [label = "9"];
    S0 -> S1 [label = "8"];
}

alpaca读取multi.regex中的内容并且将处理的结果输出到stdout中。为了直观，把这个结果用dot转换成图片就是这个样子的：https://github.com/activesys/alpaca-llama/blob/v1.0/sample/multi.png

正则表达式\d是助记符，表示[0-9]，multi.regex中的每行都是\d，在词法分析中表示同一个转换，alpaca在处理的过程中将它们合并。

自举

最后看看alpaca处理真实的描述词法的正则表达式集合。正则表达式本身也需要词法描述，正则表达式本身的词法描述也是通过正则表达式描述的。我们用alpaca来处理alpaca识别的正则表达式的词法描述正则表达式集合(T_T).

[wb@activesys sample]$ cat regex.regex 
\||\*|\+|\(|\)|\\|\.|\^|\[|\]|\-
[0-9]
[a-zA-Z]
!|"|#|$|%|&|'|,|/|:|;|<|=|>|?|@|_|`|{|}|~
\\(\||\*|\+|\(|\)|\\|\.|\^|\[|\]|\-)
\\a|\\b|\\f|\\n|\\r|\\t|\\v|\\c
\\d|\\D|\\w|\\W|\\s|\\S|\\l|\\C
[wb@activesys sample]$ alpaca.py -o regex.gv regex.regex 
[wb@activesys sample]$ dot -Tpng -oregex.png regex.gv

生成的dot脚本保存在regex.gv中https://github.com/activesys/alpaca-llama/blob/v1.0/sample/regex.gv 生成的图片保存在regex.png中https://github.com/activesys/alpaca-llama/blob/v1.0/sample/regex.png

错误消息

alpaca在解析正则表达式的时候，遇到语法错误就会立刻停止解析，并且报告语法和语义错误：

[wb@activesys sample]$ alpaca.py 
*
SyntaxError(1): Regex Syntax Error: we need "(", ".", "[" or operand, but we encount "*"!

符号*表示闭包运算，但是前面必须有一个操作数才是正确的。处理语法错误外，alpaca还会识别语义错误：

[wb@activesys sample]$ alpaca.py 
[z-a]
SyntaxError(1): Regex Semantics Error: we encount a invalid range "z-a"!

完全参考

这里只是简单的介绍的alpaca的功能，在下面这些地方可以找到完整的参考：

Add a custom footer
⚠️ **GitHub.com Fallback** ⚠️