这几天比较忙,让大家久等了。但是我语法分析篇还需要一些准备,所以今天带来一个特别娱乐项目。其实也正好想多举一些例子,介绍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:android 实现定时器
第5769行,第29列
第14112行,第8列
第16578行,第14列
第17558行,第8列
第17646行,第25列
第20351行,第34列
第22304行,第23列
第22908行,第31列
|
可见我手里这本圣经出现了8次apple(我特意看了前面,亚当和夏娃吃的是fruit,不是apple……)。如果搜microsoft的话发现圣经中并没有出现,怪不得苹果最近这么风光……
分享到:
相关推荐
编译器中c语言 词法分析器 编译器中c语言 词法分析器 编译器中c语言 词法分析器 编译器中c语言 词法分析器 编译器中c语言 词法分析器 编译器中c语言 词法分析器
C语言开发课程设计词法分析器源代码介绍 课程设计:词法分析器; 实验1:词法分析实验 实验2:语法分析实验 课程设计 设计任务: 使用词法分析的自动生成工具 Flex 生成 C/C++语言的词法分析器 ,当输入C/C++源代码...
编译器中的语法词法分析器(源代码),对初学编译器的兄弟们很有用!
用c语言写的编译器的词法分析器.输入一个文件的地址,输出一个词法分析文件.
编译器设计的第一部分 词法分析器的设计,词法关键字基本覆盖c语言,不支持引入头文件,使用c++编写,面向对象方法
编译原理课程的词法分析器 一、 实验要求 完成C--语言(C++语言子集)的词法分析器,词法分析器的输入为C--语言源代码,输出识别出单词的二元属性,填写符号表,包括关键字,标识符,界符,算符,常数,其他六大类型。...
中国矿业大学编译原理实践课程,C语言编译器词法分析器
实验一:词法语法分析器的设计与实现:建议使用词法语法生成工具如:LEX/FLEX ,YACC/BISON等专业工具完成。 实验二:符号表的设计与属性计算:设计符号表数据结构和关键管理功能。动态展现符号表变化过程。无论语法...
实现了一个简单编译器的词法分析过程,目前很多人都向学习编写编译器,可是苦于没有合适的例子做指导,现在这个程序就是为所有第一次编写编译器的孩子们准备的。believe me !请关注稍后的语法分析器
词法分析器(编译原理)
这是课程设计的一部分,只实现了中间代码生成前面的词法,语法等分析功能
Linux下的flex词法分析器实验要求: 熟练掌握词法分析,设计编译程序能够查出 C--源代码中可能包含的下 述几类错误: 1. 词法错误(错误类型 A):出现 C—词法中未定义的字符以及任何不符合 C—词法单元定义的字符; 2. ...
这个有关编译原理词法分析器的实现,使用C语言实现,比较简单。
实验一:简易词法分析,实验目的 实现一个C语言子集的词法分析程序。
《编译原理》课程实践项目,一个C语言子集的编译器,包括词法分析器和语法分析器,由Java语言实现。.zip
运用c语言写的词法分析器,完成对程序中的构词的分析功能。代码长度三百多行,上传的东东已在VC编译器中通过,和大家共同学习,参考。
编译器,词法分析器
编译器的实现 词法+语法 编译器的实现 词法+语法 编译器的实现 词法+语法
北邮《编译原理与技术》课程实验,符合课本要求的词法分析器
编译器的实现_词法分析部分_于埴尧.caj编译器的实现_词法分析部分_于埴尧.caj编译器的实现_词法分析部分_于埴尧.caj编译器的实现_词法分析部分_于埴尧.caj编译器的实现_词法分析部分_于埴尧.caj编译器的实现_词法...