CODEWITHSUNDEEP
parsingcompiler-constructiongrammar
Tyler Klement
Tyler Klement

Reputation: 41

Create a top down parser based on a custom language

Consider the language (Σ,R,S), defined by 

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

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. 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.

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

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

Upvotes: 1

Views: 196

Answers (1)

Toon Krijthe
Toon Krijthe

Reputation: 53366

The grammar can be written as:

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

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)

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.

Upvotes: 2

Related Questions