Archive

Posts Tagged ‘词法分析’

56 行代码用 Python 实现一个 Flex/Lex

October 30th, 2023 3 comments

作为 Yacc/Bison 的好搭档 Lex/Flex 是一个很方便的工具,可以通过写几行规则就能生成一个新的词法分析器,大到给你的 parser 提供 token 流,小到解析一个配置文件,都很有帮助;而用 Python 实现一个支持自定义规则的类 Flex/Lex 词法分析器只需要短短 56 行代码,简单拷贝粘贴到你的代码里,让你的代码具备基于可定制规则的词法分析功能。

原理很简单,熟读 Python 文档的同学应该看过 regex module 帮助页面最下面有段程序:

def tokenize(code):
    keywords = {'IF', 'THEN', 'ENDIF', 'FOR', 'NEXT', 'GOSUB', 'RETURN'}
    token_specification = [
        ('NUMBER',   r'\d+(\.\d*)?'),  # Integer or decimal number
        ('ASSIGN',   r':='),           # Assignment operator
        ('END',      r';'),            # Statement terminator
        ('ID',       r'[A-Za-z]+'),    # Identifiers
        ('OP',       r'[+\-*/]'),      # Arithmetic operators
        ('NEWLINE',  r'\n'),           # Line endings
        ('SKIP',     r'[ \t]+'),       # Skip over spaces and tabs
        ('MISMATCH', r'.'),            # Any other character
    ]
    tok_regex = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
    line_num = 1
    line_start = 0
    for mo in re.finditer(tok_regex, code):
        kind = mo.lastgroup
        value = mo.group()
        column = mo.start() - line_start
        if kind == 'NUMBER':
            value = float(value) if '.' in value else int(value)
        elif kind == 'ID' and value in keywords:
            kind = value
        elif kind == 'NEWLINE':
            line_start = mo.end()
            line_num += 1
            continue
        elif kind == 'SKIP':
            continue
        elif kind == 'MISMATCH':
            raise RuntimeError(f'{value!r} unexpected on line {line_num}')
        yield Token(kind, value, line_num, column)

上面这个官方文档里的程序,输入一段代码,返回 token 的:名称、原始文本、行号、列号 等。

它其实已经具备好三个重要功能了:1)规则自定义;2)由上往下匹配规则;3)使用生成器,逐步返回结果,而不是一次性处理好再返回,这个很重要,可以保证语法分析器边分析边指导词法分析器做一些精细化分析。

我们再它的基础上再修改一下,主要补充:

  • 支持外部传入规则,而不是像上面那样写死的。
  • 规则支持传入函数,这样可以根据结果进行二次判断。
  • 更好的行和列信息统计,不依赖 NEWLINE 规则的存在。
  • 支持 flex/lex 中的 “忽略”规则,比如忽略空格和换行,或者忽略注释。
  • 支持在流末尾添加一个 EOF 符号,某些 parsing 技术需要输入流末尾插入一个名为 \$ 的结束符。

对文档中的简陋例子做完上面五项修改,我们即可得到一个通用的基于规则的词法分析器。

改写后代码很短,只有 56 行:

(点击 more 展开)

Read more…

Categories: 编译原理 Tags:

Python 中使用组合方式构建复杂正则

January 17th, 2023 No comments

正则写复杂了很麻烦,难写难调试,只需要两个函数,就能用简单正则组合构建复杂正则:

比如输入一个字符串规则,可以使用 {name} 引用前面定义的规则:

# rules definition
rules = r'''
    protocol = http|https
    login_name = [^:@\r\n\t ]+
    login_pass = [^@\r\n\t ]+
    login = {login_name}(:{login_pass})?
    host = [^:/@\r\n\t ]+
    port = \d+
    optional_port = (?:[:]{port})?
    path = /[^\r\n\t ]*
    url = {protocol}://({login}[@])?{host}{optional_port}{path}?
'''

然后调用 regex_build 函数,将上面的规则转换成一个字典并输出:

# expand patterns in a dictionary
m = regex_build(rules, capture = True)

# list generated patterns
for k, v in m.items(): 
    print(k, '=', v)

结果:

protocol = (?P<protocol>http|https)
login_name = (?P<login_name>[^:@\r\n\t ]+)
login_pass = (?P<login_pass>[^@\r\n\t ]+)
login = (?P<login>(?P<login_name>[^:@\r\n\t ]+)(:(?P<login_pass>[^@\r\n\t ]+))?)
host = (?P<host>[^:/@\r\n\t ]+)
port = (?P<port>\d+)
optional_port = (?P<optional_port>(?:[:](?P<port>\d+))?)
path = (?P<path>/[^\r\n\t ]*)
url = (?P<url>(?P<protocol>http|https)://((?P<login>(?P<login_name>[^:@\r\n\t ]+)(:(?P<login_pass>[^@\r\n\t ]+))?)[@])?(?P<host>[^:/@\r\n\t ]+)(?P<optional_port>(?:[:](?P<port>\d+))?)(?P<path>/[^\r\n\t ]*)?)

用手写直接写是很难写出这么复杂的正则的,写出来也很难调试,而组合方式构建正则的话,可以将小的简单正则提前测试好,要用的时候再组装起来,就不容易出错,上面就是组装替换后的结果。

下面用里面的 url 这个规则来匹配一下:

(点击 more 展开)

Read more…

Categories: 编译原理 Tags:

转换 Intel汇编格式到 AT&T汇编风格

April 10th, 2015 1 comment

常用 MSVC写内嵌汇编需要兼容 GCC是一件头疼的事情,不是说你不会写 GCC的 AT&T风格汇编,而是说同一份代码写两遍,还要调试两遍,是一件头疼的事情,特别是汇编写了上百行的时候。于是五年前写过一个小工具,可以方便的进行转换,能把 MSVC/MASM的汇编转成纯 AT&T风格汇编,或者 GCC Inline风格汇编,自动识别寄存器和变量,还有跳转地址,并且自动导出。今天把他放上来,或许有用到的人吧。

Read more…

[业余土制] Build工具 EasyMake

July 24th, 2010 No comments

用最简单的方法描述工程信息,简化gnumake的繁琐操作,让不会用gnumake的同学们彻底解脱:

项目地址:http://code.google.com/p/easymake/

 

[业余土制] 实时汇编编译器

July 5th, 2009 3 comments

实时动态在内存中编译汇编代码,并返回函数调用指针,可用于JIT系统的后端:

项目地址:http://code.google.com/p/asmpure/

例子:

const char *AlphaBlendAsm =
"PROC C1:DWORD, C2:DWORD, A:DWORD\n"
"    movd mm0, A\n"
"    punpcklwd mm0, mm0\n"
"    punpckldq mm0, mm0\n"
"    pcmpeqb mm7, mm7\n"
"    psubw mm7, mm0\n"
"    \n"
"    punpcklbw mm1, C1\n"
"    psrlw mm1, 8\n"
"    punpcklbw mm2, C2\n"
"    psrlw mm2, 8\n"
"    \n"
"    pmullw mm1, mm7\n"
"    pmullw mm2, mm0\n"
"    paddw mm1, mm2\n"
"    \n"
"    psrlw mm1, 8\n"
"    packuswb mm1, mm1\n"
"    movd eax, mm1\n"
"    emms\n"
"    ret\n"
"ENDP\n";

void testAlphaBlend(void)
{
        CAssembler *casm;
        int c;

        int (*AlphaBlendPtr)(int, int, int);

        // create assembler
        casm = casm_create();

        // append assembly source
        casm_source(casm, AlphaBlendAsm);

        AlphaBlendPtr = (int (*)(int, int, int))casm_callable(casm, NULL);

        if (AlphaBlendPtr == NULL) {
                printf("error: %s\n", casm->error);
                casm_release(casm);
                return;
        }

        printf("==================== Alpha Blend ====================\n");

        casm_dumpinst(casm, stdout);

        printf("\nExecute code (y/n)?\n\n");

        do
        {
                c = getch();
        }
        while(c != 'y' && c != 'n');

        if(c == 'y')
        {
                int x = AlphaBlendPtr(0x00FF00FF, 0xFF00FF00, 128);
                printf("output: %.8X\n\n", x);
        }

        free(AlphaBlendPtr);
        casm_release(casm);
}

output: 7f7f7f7f

虚拟机及VmBasic编译引擎说明

April 18th, 2002 1 comment

虚拟机及VmBasic编译引擎说明

 

2001-2002期间开发的虚拟机/编译器开源项目代码和资料

  1. 关于虚拟机及其编译器的说明
  2. VmBasic开发/调试环境的介绍及说明
  3. 关于其他

所有资料可以从下面地址下载:
下载可执行 源程序下载 设计说明书

关于虚拟机及其编译器的说明

记得3DS/MAX里面实现了一个类似BASIC的脚本,Animator里面实现了一个类C的脚本语言,Autodesk公司的软件对于脚本支持的很出色,好的脚本引擎在乎平台无关性、高效性和扩充性,一个脚本引擎的需要对一个好程序来说非常迫切,于是半年前我写了一款虚拟机,最近又实现了一个类Basic的脚本编译器,特性说明:

  1. 高效性和独立于平台:由于虚拟机运行是解释二进制的字节码因此速度明显快于每次运行及时解释的脚本语言,比如Perl和PHP,而虚拟机的核心程序代码也经过数个C++编译器和平台的测试,可以毫无修改的编译运行于多个操作系统。
  2. 充分的开放:通过虚拟机的端口I/O技术,要对它进行扩充变得十分容易,VmBeta指令通过输出/输入的方法向用户自己的程序进行通讯,用户通过处理输出输入消息来达到功能的扩充,使它符合你产品的需要,具体的虚拟机实现和设计说明参考文档 vmbeta.txt
  3. 可设安全级别:通过可设置安全级别,对程序运行状态进行检控

通过半年的修改我自己觉得虚拟机够高效开放,就是vmbasic编译器写的没有多高的水准:完全没有对生成代码做优化,弄出许多繁琐的中间代码,不过还是明显快于及时解释语言,通过测试速度大概是DOS自带的QBASIC程序的三倍左右(可以通过目录下的几个算法程序来实验)。

为了检验其效率和扩充性,我将虚拟机程序扩充了一些作图功能写成了 Windows版本的,然后用vmbasic编写了一个空战小游戏,虽然由于一开始我太相信GDI而没有选择DDraw,且编译器要生成1/2左右的重复性代码,但是仍可以从游戏中看出效率来(可以用vmbide.exe打开fire.bas运行),关于编译程序VmBasic的更详细说明见basic.htm

程序说明:压缩档包括虚拟机运行程序(vmbeta.exe)VmBasic调试开发平台(vmbide.exe)四个算法例子(alex1-4.bas) 一个射击游戏例子(fire.bas)及其图片,说明帮助文档若干….

VmBasic开发/调试环境的介绍及说明:

右边的图是完整的开发环境左边是语句帮助,中间是代码编写区,下面是编译的错误和过程记录,系统热键说明:

1.F8编译成VMS文件

2.F9编译并运行程序

3.F1对VmBasic的帮助

4.Shift+F1帮助IDE

另外点击运行图表左边的图表可以查看编译出来的虚拟机汇编代码。点击工具目录,可以做一系列设置:虚拟机程序设置,预连接库设置,开发环境设置等,都是简单的东西

用VmBasic编写的射击小游戏:必须Windows版的虚拟机程序运行(扩充了GDI图形功能)

显示查看虚拟机汇编

关于其他

半年前在论坛上面看见过一些师兄们关于编译的争论,忽然有所感悟,那时刚好写了虚拟机,于是就决定为它写款语言,本来考虑写类C或者类Pascal的,但是想着Basic用起来简单,而且分析起来似乎也简单,后来我才发现虽然没有 C的编译难写但由于Basic经历了长时间的发展,语法变化很大,总的来说没有同意的规范,模块表示也不明确,就连IF语句都有好多种版本,所以一个支持函数/过程的Basic编译器我觉得比Pascal难写的多。目录DOS下有DOS环境的编译器和虚拟机,可以用来编译运行非扩展的vmbasic程序:alex1-4.bas,可以在IDE的工具->设置里面设定虚拟机的运行程序。

这是个引擎的演示版本,毕竟好的东西都不是一个人整出来的,我也会在学校不断的学习,非常欢迎来信讨论相关技术,和游戏/图形程式设计,如果你觉得这套引擎对你有价值,可以写信给我,如果你对相关的东西很感兴趣,也可以写信给我,联系方法:

成都建设路电子科技大学20013080 林伟

邮编:610000

电话:028-83200790

信箱:skywind3000@163.net

无名鸟游戏工作组制作  http://www.skywind.me

PL0 编译程序Turbo Pascal代码

April 10th, 2001 1 comment

麻雀虽小,五脏具全,对编译原理的代码以TPASCAL格式重新整理和排版,还原最原版的代码

编译版和例子下载:

 

Read more…

Wordpress Social Share Plugin powered by Ultimatelysocial