如何用JavaScript编写一个高效的词法分析器和语法解析器？-js教程-PHP中文网

如何用JavaScript编写一个高效的词法分析器和语法解析器？

狼影

发布： 2025-10-02 09:35:02

原创

561人浏览过

首先实现词法分析器将源码拆分为Token，再通过递归下降法构建AST；使用正则匹配Token并逐字符扫描，解析时按优先级分层处理表达式，确保正确性和可扩展性。

如何用javascript编写一个高效的词法分析器和语法解析器？

编写高效的词法分析器（Tokenizer）和语法解析器（Parser）是构建编译器、解释器或代码处理工具的核心部分。JavaScript 作为一门灵活的脚本语言，非常适合实现这些功能。下面从结构清晰、性能良好的角度出发，介绍如何用 JavaScript 实现一个高效的词法分析器与递归下降语法解析器。

词法分析器：将源码拆分为有意义的标记（Tokens）

词法分析器的任务是读取原始字符串输入，识别出一个个“词法单元”（Token），比如关键字、标识符、运算符、数字等。

设计要点：

使用正则表达式匹配不同类型的 Token，提高识别效率。
逐字符扫描时避免回溯，采用状态机思想提升性能。
跳过空白字符和注释以减少冗余输出。

示例代码：

立即学习“Java免费学习笔记（深入）”；

function createTokenizer(input) {
  let pos = 0;
  const tokens = [];
<p>const tokenPatterns = [
{ type: 'NUMBER',   pattern: /^\d+(.\d+)?/ },
{ type: 'IDENT',    pattern: /^[a-zA-Z_]\w<em>/ },
{ type: 'PLUS',     pattern: /^+/ },
{ type: 'MINUS',    pattern: ^- },
{ type: 'STAR',     pattern: /^\</em>/ },
{ type: 'SLASH',    pattern: /^\// },
{ type: 'EQ',       pattern: /^==/ },
{ type: 'ASSIGN',   pattern: /^=/ },
{ type: 'LPAREN',   pattern: ^$$ },
{ type: 'RPAREN',   pattern: ^$$ },
{ type: 'SEMI',     pattern: /^;/ }
];</p><p>while (pos < input.length) {
let matched = false;</p><pre class='brush:php;toolbar:false;'>// 跳过空白
if (/\s/.test(input[pos])) {
  pos++;
  continue;
}

for (const { type, pattern } of tokenPatterns) {
  const match = input.slice(pos).match(pattern);
  if (match) {
    tokens.push({ type, value: match[0] });
    pos += match[0].length;
    matched = true;
    break;
  }
}

if (!matched) {
  throw new Error(`Unexpected character at position ${pos}: ${input[pos]}`);
}

登录后复制

}

return tokens; }

这个 tokenizer 使用前向匹配，每轮尝试所有模式，找到第一个匹配项后推进位置。对于简单语言足够高效；若需更高性能，可改用 DFA 驱动的状态机。

语法解析器：根据语法规则构建抽象语法树（AST）

语法解析器接收 tokens 流，按照预定义的文法规则生成 AST。推荐使用递归下降解析法，它易于理解和调试，适合手工编写。

关键思路：

法语写作助手

法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

查看详情

每个非终结符对应一个函数，如 parseExpression()、parseStatement()。
通过函数调用栈模拟递归推导过程。
处理优先级时可用“优先级阶梯法”或 Pratt 解析器。

示例：简单算术表达式解析器

function parse(tokens) {
  let current = 0;
<p>function peek() {
return tokens[current];
}</p><p>function advance() {
return tokens[current++];
}</p><p>function expect(type) {
if (peek().type === type) {
return advance();
}
throw new Error(<code>Expected ${type}, got ${peek().type}</code>);
}</p><p>// 处理加减（最低优先级）
function parseAdditive() {
let left = parseMultiplicative();</p><pre class='brush:php;toolbar:false;'>while (peek()?.type === 'PLUS' || peek()?.type === 'MINUS') {
  const op = advance();
  const right = parseMultiplicative();
  left = {
    type: 'BinaryExpression',
    operator: op.value,
    left,
    right
  };
}

return left;

登录后复制

}

// 处理乘除（较高优先级） function parseMultiplicative() { let left = parsePrimary();

while (peek()?.type === 'STAR' || peek()?.type === 'SLASH') {
  const op = advance();
  const right = parsePrimary();
  left = {
    type: 'BinaryExpression',
    operator: op.value,
    left,
    right
  };
}

return left;

登录后复制

}

// 基本元素：数字或括号表达式 function parsePrimary() { const token = peek();

if (token.type === 'NUMBER') {
  return { type: 'NumberLiteral', value: parseFloat(token.value) };
}

if (token.type === 'LPAREN') {
  advance(); // skip '('
  const expr = parseAdditive();
  expect('RPAREN'); // must have ')'
  return expr;
}

throw new Error(`Unexpected token: ${token.value}`);

登录后复制

}

return parseAdditive(); }

该解析器实现了 +、-、*、/ 的四则运算，支持括号和正确优先级。通过分层函数控制结合性，逻辑清晰且扩展性强。