我正在用Rust编写POSIX shell实现。这带来了一些相当尴尬的要求:
如果词法分析器一次读取一个字符并允许规则设置可以由词法分析器的字符源查询的内部状态,则这两个要求都可以轻松解决(Rust不允许将状态填充到全局变量中的C解决方案)。我当前的词法分析器就是这样做的。但是,它是398行高度重复的代码,其中包括一些(不足的)测试。此代码请求自动生成。
自动生成的词法分析器通常使用基于有限自动机的表驱动设计。我对此不是很熟悉,并且想知道超前性在此设计中是固有的还是通常不使用。如果通常不使用前瞻,那么我可能可以修改现有的词法分析器生成器以执行我想要的操作;否则,我可能会停留在手写代码上。
最佳答案
这有可能是一个范围太广的问题,或者会产生包含过多观点的答案,而不是good attribute of an SO question。这是一个非常简单的问题,询问现有词法生成器算法的实现,有限自动机的编程,shell语言的词法要求以及Rust程序的特性以及其他可能的话题。
首先,让我们处理有关工具生成的词法分析器功能的问题。让我们考虑一种最常用的GNU词法分析器生成器flex
。答案是是;它可以为您构建符合您要求的词法分析器。它具有足够的灵活性,并包含足够的不同功能来完成工作(其他类似工具也是如此)。它会容易又直接吗?不必要。该工具使您可以使用内置的读取和有限状态自动机,但是您可以提供自己的输入例程,编写自己的状态机,甚至处理自己编写的代码段中的困难部分(在 C 或C++中) )。手册,教程网站,教程视频,教科书和questions here on SO中提供了许多有关如何实现此目的的示例。
当在Rust中编码时,Flex会以,C 或C++的形式生成代码,这对您有什么帮助?我们需要一个基于Rust的词法分析器。一旦可以进行文献搜索,看看有什么可用。 Wikipedia非常适合列表,并且具有list of available parser and lexer generator tools。但是,这些都不会产生Rust。但是,Rust中有这样的工具:
由于这两个都是正在进行的实验性工作,您需要自己评估它们。
另一种选择是制作自己的开源工具版本(例如
flex
)以与Rust一起使用。这可以通过两种方式完成:flex
的输出进行后处理,以将 C 代码转换为Rust代码,然后进行编译。 这些方法已经完成了几次,以实现其他新语言的定位。结果是a whole raft of compiler generator tools for a myriad of languages。
下一个问题是您手写的词法分析器代码的大小和性质。 There are standardised and recognised ways of programming finite state automata in any language. Experienced programmers would should know the pattern:
while ( NOT <<EOF>> ) {
switch ( next_symbol() ) {
case state_symbol[1]:
....
break;
case state_symbol[2]:
....
break;
default:
error(diagnostic);
}
}
甚至可以在功能上通过以下方式完成:
action[state_symbol[next_symbol()]];
可以手写相当紧凑而高效的常规语言来解析FSA来进行词法分析,但这取决于语言和算法的经验。
您广泛而又不精确的问题导致了广泛而又不精确的答案:是的,一切皆有可能,并且否,它不依赖于缓冲和回溯。
关于rust - 表驱动词法需要多少缓冲?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28844877/