根据自定义语言创建自上而下的解析器 [英] Create a top down parser based on a custom language

问题描述

考虑由

Σ = { ′(′, ′)′ }  
R = {S → SS, S → (S), S → ϵ }

1..这种语言的语法是什么?不仅是生产规则列表，因此是R吗?如果不是，那么语法与生产规则列表的区别是什么?

1. What is the grammar for this language? Isn't it just the list of production rules, therefore R? If not, what differentiates a grammar from a list of production rules?

2..然后如何基于此语法创建自上而下的解析器?我看到它提到涉及堆栈.

2. How do I then go about creating a top down parser based on this grammar? I've seen it mentioned that a stack is involved.

我的教授已经提供了一个分词器，但老实说，我不知道如何将其实现为代码(C++).

I have a tokenizer provided by my professor already, but I honestly have no idea how to go about implementing this into code (C++).

包含对DFA的引用，这些引用现在似乎已经不相关了，因此可能是对项目描述的误解

contained references to DFAs, which now seem like they're unrelated, so it was possibly a misunderstanding of the project description

推荐答案

语法可以写为:

S  = 
   | '(', S, ')', S
   ;

我为解析器添加了一些伪代码.首先是访问和操纵令牌流的功能.

I add some pseudocode for the parser. First the functions to access and manipulate the tokenstream.

IsEof: Bool // checks for end of token stream
Get: Token   // gets next token
Peek: Token // peeks next token without removing it

然后解析器. S被识别为空令牌流，或被另一个S跟随的paren集.

Then the parser. S is recognized as an empty tokenstream, or a paren set followed by another S.

Parse_S
  // If no tokens left, there is a match.
  if (IsEof) return True // OK
  // Expect at least one paren set, but possibly more
  else return (Peek == '(') && (Parse_ParenSet) && (Parse_S)

paren集是用括号括起来的S.

The paren set is an S enclosed in parenthesis.

Parse_ParenSet
  // Expect a paren set.
  if (IsEof) return False // Error
  // Expect an S enclosed in Parenthesis.
  else return (Get == '(') && (Parse_S) && (Get == ')')

现在您应该可以继续分配任务了.

Now you should be able to continue the assignment.

这篇关于根据自定义语言创建自上而下的解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！