4

我什至不知道从哪里开始编写逐字符的词法分析器。我根据给定的规则和细节为 Markdown 语言（特别是 HTML）编写了 BNF 语法规则，因此不需要添加任何内容。我现在必须设计和实现一个逐字符的词法分析器，它将我的 Markdown 语言中的源文件的词位划分为标记。这是我的 BNF 语法：

终端：

#DOCUMENT BEGIN,
#DOCUMENT END
#HEAD BEGIN,
#HEAD END,
#TITLE BEGIN,
#TITLE END,
#PARAGRAPH BEGIN,
#PARAGRAPH END,
#BOLD BEGIN,
#BOLD END,
#ITALICS BEGIN,
#ITALICS END,
#LIST BEGIN,
#LIST END,
#ITEM BEGIN,
#ITEM END,
#LINK BEGIN,
#TEXT,
#ADDRESS,
#LINK END,
#DEFINE BEGIN,
#NAME,
#VALUE,
#DEFINE END,
#USE BEGIN,
#USE END

请注意，这些终端不区分大小写。

非终端：

<document> ::= #DOCUMENT BEGIN <macro-­‐define> <head> <body> #DOCUMENT END

<head> ::= #HEAD BEGIN <title> #HEAD END | ε

<title> ::= #TITLE BEGIN <text> #TITLE END | ε

<body> ::= <inner-­‐text> <body>
           | <paragraph> <body>
           | <bold> <body>
           | <italics> <body>
           | <list> <body>
           | ε

<paragraph> ::= #PARAGRAPH BEGIN <macro-­‐define> <inner-­‐paragraph> #PARAGRAPH END

<inner-­‐paragraph> ::= <inner-­‐text> <inner-­‐paragraph>
                      | <bold> <inner-­‐paragraph>
                      | <italics> <inner-­‐paragraph>
                      | <list> <inner-­‐paragraph>
                      | ε

<inner-­‐text> ::= <macro-­‐use> <inner-­‐text>
                  | <text> <inner-­‐text>
                  | ε

<macro-­‐define> ::= #DEFINE BEGIN #NAME <text> #VALUE <body> #DEFINE END <macro-­‐define>
                    | ε

<macro-­‐use> ::= #USE BEGIN <text> #USE END | ε

<bold> ::= #BOLD BEGIN <macro-­‐define> <inner-­‐text> #BOLD END

<italics> ::= #ITALICS BEGIN <macro-­‐define> <inner-­‐text> #ITALICS END

<link> ::= #LINK BEGIN #TEXT <text> #ADDRESS <text> #LINK END

<list> ::= #LIST BEGIN #ITEM BEGIN <macro-­‐define> <inner-­‐list> #ITEM END <list-­‐items> #LIST END

<list-­‐items> ::= #ITEM BEGIN <macro-­‐define> <inner-­‐list> #ITEM END <list-­‐items> | ε

<inner-­‐list> ::= | <bold> <inner-­‐list>
                  | <italics> <inner-­‐list>
                  | <list><inner-­‐list>
                  | <inner-­‐text> <inner-­‐list>
                  | ε

<text> ::= Any plain text | ε

我们可以假设诸如“<”、“>”、“&”和“/”之类的 HTML 字符不会出现在源文件的任何文本中。我们也可以假设“#”只出现在我们的 Markdown 注释之一之前（例如，#DOCUMENT）。我认为最好有单独的 Java 类来表示令牌对象，例如：DocumentBegin、DocumentEnd、ParagraphBegin、ParagraphEnd 等。遇到的任何词法错误（例如，#DOC BEGIN）都应该作为输出报告给控制台尽可能的错误信息。遇到第一个错误后，编译器应该退出。如果遇到错误，则不应创建输出文件。

我的问题是，我知道词法分析器应该做什么，但老实说，我不知道从哪里开始编码/实现。如果您需要更多关于问题所在的解释，请询问，我可以尽力解释。这是我们为我的班级准备的一个大项目的一部分。我无法完成这部分并失去了很多分数，但现在我只需要了解它，所以一旦我们对其进行测试，我就不会那么迷失了。

4

2 回答 2

1

好的，这有点晚了，但我们开始吧。

词法分析器通常与语法（和 BNF 表示法）相关联，但两者实际上有点不同。

词法分析器将字符转换为标记，这些标记在一定程度上被处理为语法的“原子”，而解析器将标记转换为某种中间结构（通常是树）。仅关注词法分析器部分，您可以将其视为输入的低通处理，就像我们将字母处理成单词一样。

由于您已经掌握了 BNF 语法，因此您已经知道要使用的所有标记（结束词），因此将它们列成一个列表。这个想法是如何快速决定哪些字母系列将映射到列表中的每个项目。例如

#, D, E, F, I, N, E, <whitespace> => #DEFINE
#, D, O, C, U, M, E, N, T, <whitespace> => #DOCUMENT
B, E, G, I, N, <whitespace> => BEGIN
E, N, D, <whitespace> => END

在解析过程中会出现一些问题：

首先，你有很多比较要做。读入的第一个字符可能是“#”，如果是，那么您仍然有超过 20 个可能匹配的项目。这意味着您必须继续匹配到下一个字符，如果它是“D”，则仍然意味着有两个可能的匹配“#DEFINE”和“#DOCUMENT”。

其次，如果在处理完“#BEGIN”之后还有“#BEGIN”和“#BEGINNING”之类的词，则在抓住下一个字符之前，您无法在两者之间做出决定。在认为“消耗”字符的系统中抓取下一个字符会使下一个令牌的处理复杂化。可能需要窥视或前瞻，但这些会增加逻辑的复杂性以决定生成哪些令牌。

第三，您有一个通配符“文本”标记。该令牌几乎可以匹配任何东西，因此您需要对照所有其他令牌检查它，以确保您的令牌生成逻辑将始终知道它应该生成哪个令牌。

理想情况下，令牌生成器（Lexer）不依赖于任何解析来“知道”下一个令牌；但是，有些语言足够复杂，以至于解析器会向 Lexer 提供“提示”。避免这些类型的系统有助于更清洁的编译器实现；不幸的是，在一些已经存在的语言中，并不总是可以以这种方式构建东西。

所以，知道你知道该怎么做（在某种意义上你可能已经知道了）你会怎么做？

好吧，您需要某种索引来跟踪您使用的字符（即已完全转换为令牌），这样您就不会意外地给字符带来双重影响 Token 流。如果您要向前看，您需要第二个指针来“向前看”，并且您可能希望限制向前看的数量（以使逻辑不那么困难）。

然后你需要未知数量的数据结构（称为令牌）。虽然并不总是需要这样做，但我建议跟踪 Token 中的起始行号、起始字符索引、结束行号和结束字符索引。它使调试变得容易得多。此外，“捕获”令牌中的子字符串是个好主意。您可以随意称呼它，但有些人称其为令牌的“图像”。

自然，如果您的解析器可以区分不同类型的令牌，那么您应该通过某种方式将该令牌的类型存储在（或与）令牌中。偶尔有人对代币的“价值”有一个概念，它也可能被存储起来。

经过一番努力，您应该能够将一串字符推入 Lexer 并得到一个 Token 流。祝你好运。

于 2013-11-11T03:43:23.013 回答
0

我发现在 Java 中执行此操作的最好的（也就是我知道的）词法分析器称为 JFlex。我们在大学使用它来标记语言，我已经在商业上使用它来为应用程序中的特定领域语言创建语法突出显示。

JFlex 词法分析器

http://jflex.de/

杯子解析器

http://www2.cs.tum.edu/projects/cup/

关于 LALR(1) 解析器的一点点

http://en.wikipedia.org/wiki/LALR_parser

如果您需要示例（即示例代码）给我发消息，我会给您发送一些注释。尽管我确信一些大学网站（即普林斯顿）可能有一些东西，但快速谷歌并没有显示任何有用的东西。

干杯，

约翰

于 2013-11-11T02:58:52.117 回答