惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

酷 壳 – CoolShell
酷 壳 – CoolShell
H
Hacker News: Front Page
P
Palo Alto Networks Blog
T
ThreatConnect
Apple Machine Learning Research
Apple Machine Learning Research
博客园_首页
T
True Tiger Recordings
P
Privacy & Cybersecurity Law Blog
B
Blog
IT之家
IT之家
Last Week in AI
Last Week in AI
F
Full Disclosure
Hacker News: Ask HN
Hacker News: Ask HN
C
Comments on: Blog
Microsoft Azure Blog
Microsoft Azure Blog
C
Cybersecurity and Infrastructure Security Agency CISA
Microsoft Security Blog
Microsoft Security Blog
博客园 - 【当耐特】
N
News and Events Feed by Topic
NISL@THU
NISL@THU
腾讯CDC
雷峰网
雷峰网
Security Latest
Security Latest
李成银的技术随笔
M
Microsoft Research Blog - Microsoft Research
L
LangChain Blog
L
Lohrmann on Cybersecurity
cs.CL updates on arXiv.org
cs.CL updates on arXiv.org
C
Check Point Blog
Y
Y Combinator Blog
Recent Announcements
Recent Announcements
博客园 - Franky
N
News | PayPal Newsroom
V
V2EX
A
About on SuperTechFans
The Register - Security
The Register - Security
月光博客
月光博客
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Google Online Security Blog
Google Online Security Blog
MyScale Blog
MyScale Blog
Cisco Talos Blog
Cisco Talos Blog
Vercel News
Vercel News
WordPress大学
WordPress大学
C
Cyber Attacks, Cyber Crime and Cyber Security
The Hacker News
The Hacker News
IntelliJ IDEA : IntelliJ IDEA – the Leading IDE for Professional Development in Java and Kotlin | The JetBrains Blog
IntelliJ IDEA : IntelliJ IDEA – the Leading IDE for Professional Development in Java and Kotlin | The JetBrains Blog
爱范儿
爱范儿
A
Arctic Wolf
L
LINUX DO - 最新话题
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More

博客园 - 装配脑袋

Windows Azure一些小技巧集合 C++ AMP实战:绘制曼德勃罗特集图像 GPU并行计算版函数图像生成器 自己动手开发编译器(十二)生成托管代码 自己动手开发编译器(十一)语义分析 自己动手开发编译器(十)miniSharp语法分析器 自己动手开发编译器(九)CPS风格的解析器组合子 自己动手开发编译器(八)用Linq编写解析器组合子 自己动手开发编译器(七)递归下降的语法分析器 自己动手开发编译器(六)上下文无关语言和文法 自己动手开发编译器(五)miniSharp语言的词法分析器 - 装配脑袋 自己动手开发编译器(四)利用DFA转换表建立扫描器 自己动手开发编译器(三)有穷自动机 自己动手开发编译器(二)正则语言和正则表达式 自己动手开发编译器(一)编译器的模块化工程 自己动手开发编译器(零)序言 DirectCompute & DirectX 11 计算着色器编程简介(翻译) 趣味问题:你能用Reflection.Emit生成这段代码吗?(答案) 趣味问题:你能用Reflection.Emit生成这段代码吗?
自己动手开发编译器特别篇——用词法分析器解决背诵圣经问题
装配脑袋 · 2011-06-16 · via 博客园 - 装配脑袋

这几天比较忙,让大家久等了。但是我语法分析篇还需要一些准备,所以今天带来一个特别娱乐项目。其实也正好想多举一些例子,介绍VBF.Compilers.Scanner库的使用方法。今天的问题来自于一道腾讯的PHP面试题,原题如下:

我们碰到了大麻烦,一个新来的传教士惹恼了上帝,上帝很愤怒,要求我们把圣经背熟,直至他说哪个单词,我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员,那么髟助我们完成这个不可能的任务吧。

要求如下:

1)/myworks/example/bbe.txt,98版本英文圣经一本

2)输入部分要求如下:php ./example.php [单词]

3)输出部分如下:[单词] 1,2 2,4 5,6表示:此单词在1行2列(第二个单词),2行4列...

说明:

1)此文本4MB之巨...

2)单词的含义:由英文字母(大小写),数字(0-9)组成的串

3)提供给你的机器OS为ubuntu 9.10,内存只有1G,而且,很不幸的,其中700M用来做了别的

4)上机考试不允许上网,但我装了man文档以及读取CHM以及PDF的阅读器,在电脑的桌面的CHM文件夹中,有相应的PHP参考手册

5)算法复杂度要求不能大于O(N^2)(就是N的平方)

6)什么?PHP低效且用起来不顺手,好的,你可以用别的语言来实现。但注意:提供给你的机器上只有python 2.4/perl 5.8/gcc[g++] 4.1

原题是要求使用PHP的,我们只是娱乐,不是真面试,当然就无视各种规定了。这道题不必使用词法分析的原理,可以写出很快的算法。但是用词法分析库来实现也是个不错的注意,因为DFA词法分析是O(N)的算法而且实际执行起来效率相当不错。下面我们就用VBF.Compilers.Scanner库来解决这道题:

Imports VBF.Compilers.Scanners
Imports VBF.Compilers.Scanners.RegularExpression
Imports System.IO

Module Program

    Sub Main(args As String())
        Dim findword = args(0)

        Dim bibleLexicon As New Lexicon()
        Dim lex = bibleLexicon.DefaultLexer

        '定义要寻找单词的词法
         Dim TARGET = lex.DefineToken(Literal(findword))
        '定义一般单词的词法
         Dim WORD = lex.DefineToken((Range("0"c, "9"c) Or
                                    Range("a"c, "z"c) Or
                                    Range("A"c, "Z"c)).Many1)
        '定义换行
         Dim LF = lex.DefineToken(Symbol(vbLf) Or Literal(vbCrLf))
        '定义其他所有符号均忽略
         Dim OTHER = lex.DefineToken(Range(ChrW(0), ChrW(255)))

        Dim bibleScanner As New PeekableScanner(bibleLexicon.CreateScannerInfo())
        bibleScanner.SetSkipTokens(OTHER.Index)

        Using sr As New StreamReader("bible.txt")
            Dim source As New SourceReader(sr)
            bibleScanner.SetSource(source)

            Dim scannerWatch As New Stopwatch

            Dim lines = 1, columns = 1, totalwords = 0, targetwords = 0
            scannerWatch.Start()
            Do While bibleScanner.Peek() <> bibleScanner.ScannerInfo.EndOfStreamTokenIndex
                Dim x As Lexeme = bibleScanner.Read()

                Select Case x.TokenIndex
                    Case TARGET.Index
                        Console.WriteLine("第{0}行,第{1}列", lines, columns, x.Value)
                        columns += 1
                        targetwords += 1
                        totalwords += 1
                    Case WORD.Index
                        columns += 1
                        totalwords += 1
                    Case LF.Index
                        lines += 1
                        columns = 1
                End Select
            Loop
            scannerWatch.Stop()

            Console.WriteLine("总单词数: " & totalwords)
            Console.WriteLine("目标单词出现次数: " & targetwords)
            Console.WriteLine("消耗时间: " & scannerWatch.ElapsedMilliseconds)
        End Using
    End Sub

End Module

这就是完整的代码。为了统计是第几个单词,我们按照题目的规定,定义了一般单词的词法,目标单词的词法,并且忽略所有其他字符(设定为SkipTokens)。分析过程就是不断读取下一个单词,直到文件的末尾。注意,这次我展示的是具有超前查看功能的PeekableScanner类,它可以超前查看任意多个单词,其实也可以用普通的Scanner而且性能更好。现在大家可以试试圣经中出现了什么单词,比如我们试一下apple:

第5769行,第29列
第14112行,第8列
第16578行,第14列
第17558行,第8列
第17646行,第25列
第20351行,第34列
第22304行,第23列
第22908行,第31列

可见我手里这本圣经出现了8次apple(我特意看了前面,亚当和夏娃吃的是fruit,不是apple……)。如果搜microsoft的话发现圣经中并没有出现,怪不得苹果最近这么风光……

源代码和圣经文件可以在这里下载:BibleFinder.7z

另外有不少同学问虎书是什么书,这里有龙书、虎书和鲸书的介绍:http://unistd.blog.51cto.com/1126453/260372。下一篇开始我们正式进入语法分析部分。希望大家继续关注我的VBF项目:https://github.com/Ninputer/VBF 和我的微博:http://weibo.com/ninputer 多谢大家支持!