介绍
解析器在日常生活中可以使用各种应用，您可能每天使用一些解析器。 Babel，webpack，eslint，prettier和jscodeshift。所有这些都在幕后，运行一个解析器，该解析器操纵抽象的语法树（AST）来做您需要的事情 - 我们稍后再谈论，不用担心。
本文的想法是介绍Lexing和解析的概念，使用JavaScript实施它们来分析JSON中的表达。目标是将此过程分为函数，解释这些功能，最后，您是否实现了JSON解析器生成AST。
值得注意的是，我的存储库是开放的，您可以访问here。
Lexing
lexer将负责将表达式转换为代币。这些令牌是具有分配含义的可识别元素。
您可以通过几种方式将这些令牌分开，例如identifier，keyword，delimiter，operator，literal和comment。
。 { "type": "LEFT_BRACE", "value": undefined }是定界符的一个示例。 { "type": "STRING", "value": "name" }是字面的示例。
示例：{"name":"Vitor","age":18}
[
{ "type": "LEFT_BRACE", "value": undefined },
{ "type": "STRING", "value": "name" },
{ "type": "COLON", "value": undefined },
{ "type": "STRING", "value": "Vitor" },
{ "type": "COMMA", "value": undefined },
{ "type": "STRING", "value": "age" },
{ "type": "COLON", "value": undefined },
{ "type": "NUMBER", "value": "18" },
{ "type": "RIGHT_BRACE", "value": undefined }
]
请注意，在词汇分析中，您将表达式分为令牌，每个令牌都有其识别。
为此，让我们首先了解我们将完全做什么。 lexer函数的想法是接收类型字符串的参数并返回一系列令牌，这将是我们已经看到和讨论的特定类型信息的JSON。
为了实现这一目标，我们将创建一个称为current的变量，该变量将存储由lexer分析的input中的字符的当前位置。换句话说，它代表了当前在我们的JSON中的位置。此外，我们将拥有一个称为tokens的常数，该数组将最终保持我们的所有令牌。
export const lexer = (input: string): Token[] => {
let current = 0;
const tokens: Token:[] = [];
}
现在，我们需要运行一个循环，该循环将迭代直到处理输入的所有字符。
请注意，可以将所有这些
if块重构为switch语句。但是，我遵循了命令的风格。
export const lexer = (input: string): Token[] => {
let current = 0
const tokens: Token[] = []
while (current < input.length) {
let char = input[current]
if (char === '{') {
tokens.push(createToken(TOKEN_TYPES.LEFT_BRACE))
current++
continue
}
if (char === '}') {
tokens.push(createToken(TOKEN_TYPES.RIGHT_BRACE))
current++
continue
}
if (char === '[') {
tokens.push(createToken(TOKEN_TYPES.LEFT_BRACKET))
current++
continue
}
if (char === ']') {
tokens.push(createToken(TOKEN_TYPES.RIGHT_BRACKET))
current++
continue
}
if (char === ':') {
tokens.push(createToken(TOKEN_TYPES.COLON))
current++
continue
}
if (char === ',') {
tokens.push(createToken(TOKEN_TYPES.COMMA))
current++
continue
}
const WHITESPACE = /\s/
if (WHITESPACE.test(char)) {
current++
continue
}
const NUMBERS = /[0-9]/
if (NUMBERS.test(char)) {
let value = ''
while (NUMBERS.test(char)) {
value += char
char = input[++current]
}
tokens.push(createToken(TOKEN_TYPES.NUMBER, value))
continue
}
if (char === '"') {
let value = ''
char = input[++current]
while (char !== '"') {
value += char
char = input[++current]
}
char = input[++current]
tokens.push(createToken(TOKEN_TYPES.STRING, value))
continue
}
if (
char === 't' &&
input[current + 1] === 'r' &&
input[current + 2] === 'u' &&
input[current + 3] === 'e'
) {
tokens.push(createToken(TOKEN_TYPES.TRUE))
current += 4
continue
}
if (
char === 'f' &&
input[current + 1] === 'a' &&
input[current + 2] === 'l' &&
input[current + 3] === 's' &&
input[current + 4] === 'e'
) {
tokens.push(createToken(TOKEN_TYPES.FALSE))
current += 5
continue
}
if (
char === 'n' &&
input[current + 1] === 'u' &&
input[current + 2] === 'l' &&
input[current + 3] === 'l'
) {
tokens.push(createToken(TOKEN_TYPES.NULL))
current += 4
continue
}
throw new TypeError('I dont know what this character is: ' + char)
}
return tokens
}
此代码似乎很复杂，但实际上很简单。在我的循环内，我首先定义可变char，该变量将存储当前正在分析的字符在循环的迭代中。然后，对于每种类型的字符，我们想要一个特定的动作。
如果char等于{，我们将其推入令牌数组，传递给代币的枚举，这将是每个令牌的名称。
export enum TOKEN_TYPES {
LEFT_BRACE = 'LEFT_BRACE',
RIGHT_BRACE = 'RIGHT_BRACE',
LEFT_BRACKET = 'LEFT_BRACKET',
RIGHT_BRACKET = 'RIGHT_BRACKET',
COLON = 'COLON',
COMMA = 'COMMA',
STRING = 'STRING',
NUMBER = 'NUMBER',
TRUE = 'TRUE',
FALSE = 'FALSE',
NULL = 'NULL',
}
在函数createToken中，它仅返回一个用type或value的对象。
export const createToken = (type: TOKEN_TYPES, value?: string): Token => {
return {
type,
value,
}
}
之后，它将+1增加到current变量，以移至我们的字符串中的下一个char。这个过程非常重复且直接。我不会解释其中的每个人，但是值得关注那些与模式有点偏离的人。
if (char === '"') {
let value = ''
char = input[++current]
while (char !== '"') {
value += char
char = input[++current]
}
char = input[++current]
tokens.push(createToken(TOKEN_TYPES.STRING, value))
continue
}
if (
char === 't' &&
input[current + 1] === 'r' &&
input[current + 2] === 'u' &&
input[current + 3] === 'e'
) {
tokens.push(createToken(TOKEN_TYPES.TRUE))
current += 4
continue
}
if (
char === 'f' &&
input[current + 1] === 'a' &&
input[current + 2] === 'l' &&
input[current + 3] === 's' &&
input[current + 4] === 'e'
) {
tokens.push(createToken(TOKEN_TYPES.FALSE))
current += 5
continue
}
if (
char === 'n' &&
input[current + 1] === 'u' &&
input[current + 2] === 'l' &&
input[current + 3] === 'l'
) {
tokens.push(createToken(TOKEN_TYPES.NULL))
current += 4
continue
}
如果char等于"，我们输入一个循环以继续读取后续字符，直到我们找到另一个引号标记，因为这表示字符串的末尾。在此循环期间读取的所有字符都串联到“值”变量中。然后，将新令牌添加到“令牌”数组中。
其他行用于设置布尔值。如果当前字符为“ f”，而后续字符构成了false词，则为tokens数组添加false。对true重复相同的过程。
在所有情况下，current变量都会增加以指向要处理的下一个字符，就像我们在整个代码中所做的那样。
解析
解析器负责将一系列令牌转换为数据结构，在这种情况下，AST。
从“ ML中的现代编译器实施”一书中获取的AST的例证。
抽象语法树（AST）是代表程序的句法结构的数据结构。在AST中，有几个节点，每个节点代表程序的有效句法结构。例如：
parser: {
"type": "Program",
"body": [
{
"type": "ObjectExpression",
"properties": [
{
"type": "Property",
"key": {
"type": "STRING",
"value": "name"
},
"value": {
"type": "StringLiteral",
"value": "Vitor"
}
},
{
"type": "Property",
"key": {
"type": "STRING",
"value": "age"
},
"value": {
"type": "NumberLiteral",
"value": "18"
}
}
]
}
]
}
这是我一开始就举例说明的JSON的AST。在此示例中，我们共有8个节点。 Program节点代表主程序。 ObjectExpression代表对象，Property代表对象内的属性，由键和值组成。 STRING代表用作键的字符串，字符串Literal代表属性中的一个字符串，而NumberLiteral表示属性中的数字值。
通过AST，可以优化代码，将一个代码转换为另一个代码，执行静态分析，生成代码等。例如，您可以实现新的语法，创建解析器并生成正常执行的JavaScript代码。
要生成我们的AST，我们将需要一个接收我们的令牌数组的函数，通过它迭代，并根据其遇到的令牌生成AST。为此，我们将创建一个称为walk的函数，该函数将穿越令牌并返回AST的节点。
export const parser = (tokens: Array<{ type: string; value?: any }>) => {
let current = 0;
const walk = () => {
let token = tokens[current];
if (token.type === TOKEN_TYPES.LEFT_BRACE) {
token = tokens[++current];
const node: {
type: string;
properties?: Array<{ type: string; key: any; value: any }>;
} = {
type: 'ObjectExpression',
properties: [],
};
while (token.type !== TOKEN_TYPES.RIGHT_BRACE) {
const property: { type: string; key: any; value: any } = {
type: 'Property',
key: token,
value: null,
};
token = tokens[++current];
token = tokens[++current];
property.value = walk();
node.properties.push(property);
token = tokens[current];
if (token.type === TOKEN_TYPES.COMMA) {
token = tokens[++current];
}
}
current++;
return node;
}
我们执行的第一次检查是当前令牌是否为{。如果是这样，我们会创建一个类型ObjectExpression的新节点，并通过以下令牌迭代，将它们添加为对象的属性，直到我们找到键的末端，即}。每个属性由Property类型的节点表示。该Property类型具有由walk()函数生成的值，该值递归称为。
请注意，我使用tokens[++current]。这是将光标推向下一个令牌。如果找到了（逗号）的类型令牌，我们再次推进光标以跳过逗号。
其余的代码与我刚刚解释的内容非常相似，因此值得努力的努力，试图自己理解或实施其余部分。这不是很复杂。
最后，我创建了常数ast，它将包含由walk()函数生成的类型Program和AST的主体。 while循环确保current不超过令牌阵列的大小。
之后，我们简单地退还了AST。
export const parser = (tokens: Array<{ type: string; value?: any }>) => {
let current = 0
const walk = () => {
let token = tokens[current]
if (token.type === TOKEN_TYPES.LEFT_BRACE) {
token = tokens[++current]
const node: {
type: string
properties?: Array<{ type: string; key: any; value: any }>
} = {
type: 'ObjectExpression',
properties: [],
}
while (token.type !== TOKEN_TYPES.RIGHT_BRACE) {
const property: { type: string; key: any; value: any } = {
type: 'Property',
key: token,
value: null,
}
token = tokens[++current]
token = tokens[++current]
property.value = walk()
node.properties.push(property)
token = tokens[current]
if (token.type === TOKEN_TYPES.COMMA) {
token = tokens[++current]
}
}
current++
return node
}
if (token.type === TOKEN_TYPES.RIGHT_BRACE) {
current++
return {
type: 'ObjectExpression',
properties: [],
}
}
if (token.type === TOKEN_TYPES.LEFT_BRACKET) {
token = tokens[++current]
const node: {
type: string
elements?: Array<{ type?: string; value?: any }>
} = {
type: 'ArrayExpression',
elements: [],
}
while (token.type !== TOKEN_TYPES.RIGHT_BRACKET) {
node.elements.push(walk())
token = tokens[current]
if (token.type === TOKEN_TYPES.COMMA) {
token = tokens[++current]
}
}
current++
return node
}
if (token.type === TOKEN_TYPES.STRING) {
current++
return {
type: 'StringLiteral',
value: token.value,
}
}
if (token.type === TOKEN_TYPES.NUMBER) {
current++
return {
type: 'NumberLiteral',
value: token.value,
}
}
if (token.type === TOKEN_TYPES.TRUE) {
current++
return {
type: 'BooleanLiteral',
value: true,
}
}
if (token.type === TOKEN_TYPES.FALSE) {
current++
return {
type: 'BooleanLiteral',
value: false,
}
}
if (token.type === TOKEN_TYPES.NULL) {
current++
return {
type: 'NullLiteral',
value: null,
}
}
throw new TypeError(token.type)
}
const ast = {
type: 'Program',
body: [],
}
while (current < tokens.length) {
ast.body.push(walk())
}
return ast
}
const tokens = lexer('{"name":"Vitor","age":18}')
console.log('tokens', tokens)
const json = parser(tokens)
console.log('parser:', JSON.stringify(json, null, 2))
解析可能很有趣，但实际上，它并不经常写，您可能不需要编写自己的解析器。例如，如果您正在实施编程语言，那么已经有各种工具可以为您完成此工作，例如Ocamllex，Menhir或近乎近的工具。
也必须注意，由于这是一篇介绍性的文章，因此我没有涵盖不同的令牌化和解析技术，例如LR(0)，LR(1)，SLR(1)等。但是，请注意，这些技术存在，您以及您都存在。可以对它们进行更多研究。也有许多涵盖这些主题的书。
如果您想查看流行语言的AST，我推荐AST Explorer。它支持各种语言，您可以查看完整的AST并通过节点导航。如果您想进一步走，可以尝试从现有解析器中复制一些逻辑并自行实现，例如根据优先顺序计算表达式，例如：1 + 2 * 3（7，而不是9）。
如果您有兴趣了解更多信息，我推荐“ ML中的现代编译器实施”一书。尽管标题为ML，但您可以在不必编写ML代码的情况下进行研究，因为C，C ++和Java中还有其他版本。