如何在Javascript中实现词法分析

Question

嘿伙计们,谢谢你的阅读

我目前正在尝试使用Google风格的计算器.您输入一个字符串,它确定是否可以计算并返回结果.

我从基础开始慢慢开始:+ - / *和括号处理.

我愿意随着时间的推移改进计算器,并且在前一段时间学习了一些关于词法分析的知识,我构建了一个令牌列表和相关的正则表达式模式.

这种工作很容易适用于Lex和Yacc等语言,除了我正在开发一个仅限Javascript的应用程序.

我试图将这个想法转录成Javascript,但我无法弄清楚如何以干净漂亮的方式处理所有内容,尤其是嵌套的括号.

---

分析

让我们定义一个计算器查询:

// NON TERMINAL EXPRESSIONS //
query     -> statement
query     -> ? // means end of query

statement -> statement operator statement
statement -> ( statement )
statement -> prefix statement
statement -> number

number    -> integer
number    -> float

// TERMINAL EXPRESSIONS //
operator  -> [+*/%^-]

prefix    -> -

integer   -> [0-9]+

float     -> [0-9]+[.,][0-9]+

---

使用Javascript

词法分析包括验证没有任何东西看起来不像终端表达式之一:运算符,前缀,整数和浮点数.哪个可缩短为一个正则表达式:

(我添加了空格以使其更具可读性)

var calcPat = 
/^ (\s*
    ( ([+/*%^-]) | ([0-9]+) | ([0-9]+[.,][0-9]+) | (\() | (\)) )
)+ \s* $/;

如果此测试通过,则查询在词法上是正确的,需要进行语法检查以确定是否可以计算.这是棘手的部分

我不打算粘贴代码,因为它不干净也不容易理解,但我将解释我遵循的过程以及为什么我卡住了:

我创建了一个名为isStatement(string)call 的方法,它应该递归调用自己.主要思想是将字符串拆分为"潜在"语句,并检查它们是否真的是语句并完全形成一个语句.
流程如下:

- 如果前两个令牌是一个数字后跟一个运算符:

- 然后,
- 如果剩下的只是一个标记而且它是一个数字:
---那么这是一个声明.
---否则,检查剩余的令牌是否形成一个声明(递归调用)

-Else,如果第一个标记是括号 - 那么
,查找匹配的右括号并检查里面的内容是否是一个语句(递归)
- 还要检查括号后是否有什么东西以及它是否与括号相关时形成一个语句结构体.

---

有什么问题 ？

我的问题是,当有嵌套结构时,我找不到匹配的括号.我怎样才能做到这一点 ？此外,正如您所看到的,这不是一种特别通用且干净的语法检查算法.你有什么想法改善这种模式吗？

非常感谢您花时间阅读所有内容.盖尔

(PS:正如你可能注意到的那样,我不是母语为英语的人!对于错误和所有错误抱歉!)

Answer 1

你对词法分析有了正确的认识,但你似乎对令牌语法和语言语法之间的区别感到困惑.这是两件不同的事情.

• 该令牌文法是一组描述该令牌将被解析的语言模式(通常正则表达式).正则表达式是字符集上的表达式.

• 该语言的语法(或目标语法,我想)是要分析语言的语法.该语法以令牌表示.

您不能编写正则表达式来解析代数表示法.你不能.你可以为它编写语法,但它不是常规语法.你想要做的是识别单独的标记,在你的情况下,你可以使用正则表达式来完成你所拥有的标记.诀窍在于你并没有真正将该表达式应用于要解析的整个句子.相反,您希望匹配句子中当前点的标记.

现在,因为你有Javascript正则表达式可以使用,你可以想出一个旨在匹配一串令牌的正则表达式.这样做的诀窍是提出一种方法来识别哪些令牌与可能性列表相匹配.Javascript正则表达式引擎可以返回组的数组,所以也许你可以在其上构建一些东西.

编辑 - 我正在尝试弄清楚如何将一个(某种程度上)通用的标记生成器组合在一起,从一个单独的正则表达式列表(每个标记一个)开始.这可能不是很复杂,而且周围有很多乐趣.