如何在Javascript中实现词法分析

Question

大家好，感谢您的阅读

我目前正在尝试做一个谷歌风格的计算器。你输入一个字符串，它判断是否可以计算并返回结果。

我慢慢地开始基础知识：

+ - / *

和括号处理。

我愿意随着时间的推移改进计算器，并且不久前学习了一些词法分析，我构建了一个标记列表和相关的正则表达式模式。

此类工作很容易适用于 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)

的方法，该方法应该递归地调用自身。主要思想是将字符串拆分为“潜在”语句，并检查它们是否确实是语句并形成一个整体。
流程如下：

-如果前两个标记是数字后跟运算符：

-那么，
-- 如果剩下的只是一个令牌并且是一个数字：
--- 那么这是一个声明。
--- 否则，检查剩余的标记是否形成语句（递归调用）

-否则，如果第一个标记是括号
-然后，找到匹配的右括号并检查里面是否是语句（递归）
-- 还要检查右括号后面是否有内容，以及与括号结构关联时是否形成语句。

---

有什么问题吗？

我的问题是，当存在嵌套结构时，我找不到匹配的括号。 我该怎么做？另外，正如你所看到的，这不是一个特别通用和干净的语法检查算法。您有什么想法可以改进这种模式吗？

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

（PS：正如您可能注意到的那样，我不是以英语为母语的人！对于错误和所有错误深表歉意！）

Answer 1

您对词法分析的理解是正确的，但您似乎对标记语法和语言语法之间的区别感到困惑。这是两个不同的事情。

• 标记语法是一组模式（通常是正则表达式），用于描述要解析的语言的标记。正则表达式是字符集上的表达式。

• 语言语法（我想是目标语法）是您要解析的语言的语法。该语法用标记来表达。

您无法编写正则表达式来解析代数符号。您就是不能。您可以为其编写语法，但这不是常规语法。您想要做的是识别单独的标记，在您的情况下，可以使用类似于您所拥有的正则表达式来完成。诀窍在于，您并没有真正将该表达式应用于要解析的整个句子。相反，您想要匹配句子中当前点的标记。

现在，因为您已经可以使用 Javascript 正则表达式，所以您可以想出一个旨在匹配标记字符串的正则表达式。这样做的技巧是想出一种方法来识别哪个标记与可能性列表中的匹配。 Javascript 正则表达式引擎可以给你返回组数组，所以也许你可以在此基础上构建一些东西。

edit - 我正在尝试弄清楚如何从一系列单独的正则表达式（每个标记一个）开始组合一个（某种程度上）通用的标记生成器构建器。它可能不是很复杂，而且会很有趣。