Estoy escribiendo un analizador para un lenguaje de marcado de nicho como Markdown. Para que las cosas sean más fáciles de entender, solo usaré Markdown como ejemplo.

Investigué un poco y aprendí que la forma convencional de analizar un documento de descuento en un AST consta de los siguientes pasos:

1. Analice el documento en una matriz de tokens.
2. Transforma los tokens en un AST.

Tengo un problema con el primer paso. La mayoría de los tutoriales en línea usan expresiones regulares para hacerlo. aquí hay un ejemplo escrito en javascript:

 function getTokensByRule(text, rule) { const tokens = []; let match = rule.exec(text); do { tokens.push(match); } while((match = rule.exec(text)) !== null); return tokens; } function getTokens(text) { // overly simplified rules, there may be a lot more in reality const rules = { italic: /\*[^*]*\*/g, code: /`[^`]*`/g, }; const tokens = []; for (const ruleName in rules) { const rule = rules[ruleName]; tokens.push(...getTokensByRule(text, rule)) } return tokens; } const tokens = getTokens("some `markdown` *texts*"); console.log(tokens); // output: // [ // [ // '*texts*', // index: 16, // input: 'some `markdown` *texts*', // groups: undefined // ], // [ // '`markdown`', // index: 5, // input: 'some `markdown` *texts*', // groups: undefined // ] // ]

Funciona, pero veo un problema en ello: esto probablemente sería lento. Analiza el documento contra cada regla de expresiones regulares. La complejidad del tiempo estaría cerca de O(n * r) , donde n es la longitud del documento y r es el número de reglas de expresiones regulares.

Entonces mi pregunta es, ¿es esta la forma convencional de analizar el lenguaje de rebajas? ¿Hay alguna forma más rápida o mejor de lograrlo?