当前位置：文江博客话题详情

语法帮助（自动机理论）？

发布于 2024-12-15 05:30:18 字数 182 浏览 3 评论 0原文

大家好，我有一个问题，关于 Automaton 的简单问题，我不确定这是否是提出此类问题的正确位置。实际上，今年我有一门课程《编译器构建》，如果有人知道一些好的资源，最好在这里发布。

首先我有一个非常基本的问题：例如我有一个像这样的表达式： 2+3*5 ，如何为这个表达式编写语法？我的意思是一个模棱两可的例子和一个明确的例子谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

眼趣 2024-12-22 05:30:18

你不能“为[一个]表达式编写语法”。语法是产生式的规则。一个简单的例子是：

S -> (S)
S -> SS
S -> [empty]

你能看出这个语法的作用吗？

本质上，这允许您生成诸如“”、“()”、“((()())())”之类的字符串。请注意，我说的是“生成” - 从逻辑上讲，您从一个“S”开始，然后从那里开始，用右侧的一些“生产”替换每个 S。但关键是，从形式意义上讲，通过此方法生成的任何字符串都是“语法正确的”。

解析与此相反 - 将字符串转换为相应的产生式顺序。如果可以通过多种方式完成，则语法是不明确的。

当您编写编译器时，首先需要对输入进行“lex”处理。 2+3*5 应该被词法成 NUM ADD NUM TIMES NUM 之类的东西（每个都是一个令牌）。然后，您根据语法解析标记以构建“语法树”，可能类似于：

  _ + _
2        *
      3/   \5

您需要编写生产规则，以便唯一可以生成有效的字符串。这有点棘手，也有点艺术，所以如果没有更多细节，我无能为力。

优先级由不同的非终结符（例如 S 和 T）处理。真正的解析器将有数十个。 C有数百个。通过巧妙地安排它们，您可以迫使某些事物先于其他事物进行匹配。

You can't "write a grammar for [an] expression". Grammars are rules for production. A simple example is:

S -> (S)
S -> SS
S -> [empty]

Can you see what this grammar does?

Essentially, this allows you to generate strings like "", "()", "((()())())". Note I said "generate" - logically, you start with a single "S", and work up from there, replacing each S with some "production" on the right. But the key is that any string you generate by this method is "grammatically correct", in a formal sense.

Parsing is the reverse of this - turning a string into the corresponding order of productions. A grammar is ambiguous if this can be done in more than one way.

When you're writing a compiler, first you need to "lex" the input. 2+3*5 should be lexed into something like NUM ADD NUM TIMES NUM (each one is a token). Then you parse the tokens based on a grammar to build a "syntax tree", perhaps something like:

  _ + _
2        *
      3/   \5

You'll need to write the rules for production such that valid strings are the only things that can be generated. It's a little tricky, and a bit of an art, so I can't help much without more details.

Precedence is handled with different nonterminals (S and T, for example). A real parser will have dozens of them. C has hundreds. By skillfully arranging them, you force certain things to be matched ahead of others.

回复收藏 0 原文

~没有更多了~