0
$\begingroup$

In many programming language string is a token.

For example:

 token               ::= '"' string
                       | digit nat

 string              ::= char string
                       | '"'

 nat                 ::= digit nat
                       | ϵ

This is a LL(1) grammar for some programming language's toke grammar.

When parsing a string, there is no need to check follow set, because there is a " at the end of each string.

Comparing with nat, string is more easy to parse.

My question is

Is there any official terminology about this kind of grammar?

Thanks.

Editing:

There was some mistake in the original grammar, thanks @rici for pointing out my mistakes.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

FOLLOW sets are not used in the parsing of either string or nat. In both cases, the parser merely needs to determine if the input is in a set of valid symbols. In the case of nat, the valid symbols are digits; in the case of string, they are characters other than ". (In real languages, the parser would also be checking for \). But in both cases, a check is necessary, and there's no good criterion for saying one test is "simpler" than another. (In practice, both checks are likely to be a simple table lookup. So they're O(1).)

FOLLOW sets are only needed when the grammar contains ε productions. Even then, the parser's actions are not complicated. What is more complicated is building the parser, something which only happens once. It's not really that big of a deal, but it's sufficiently notable that "ε-free grammars" are a thing. I don't think there's any common vocabulary to describe the difference between explicitly and implicitly-terminated repetition, and any way the distinction will be very hard to define strictly. Your string would be parsed by a parser which used a different rule to collect the trailing ", and it's quite possible that the two parsers end up with the same implementation.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Hi, thank you for your reply. But what I mean is when parsing a token, when the head char of the input is a ", we can enter into a STRING State, then we check any chars until meet another ", then we can leave the STRING State and go to a FINAL State. $\endgroup$
    – chansey
    Jul 20, 2020 at 15:27
  • $\begingroup$ Comparing with nat, this strategy is impossible, because nat has a ϵ production. We must check the follow-set of nat. $\endgroup$
    – chansey
    Jul 20, 2020 at 15:27
  • $\begingroup$ In other words, for string token, we have two ways to write the grammar. One is in the question, another way is token ::= '"' string '"' | nat string ::= char string | ϵ nat ::= digit nat | ϵ If you write grammar like this, then we need check string's follow set, because now string has a ϵ production. But for nat token, there is only one way to write, it always has a ϵ production.. $\endgroup$
    – chansey
    Jul 20, 2020 at 15:27
  • 1
    $\begingroup$ @chansey: Writing nat with an ϵ production is an error. A nat needs to have at least one digit. You're correct that the alternative grammar for string needs an ϵ production. $\endgroup$
    – rici
    Jul 20, 2020 at 15:28
  • 1
    $\begingroup$ @chansey: That's what happens when you using LL(1) parsers, I guess. I'd write that as token ::= string | nat; string ::= '"' char-list '"'; char-list ::= ϵ | char-list char; nat ::= digit | nat digit, which is LR(1) and (imho) clearer. In practice, scanners use regular expressions which are less powerful and frequently ambiguous (but the ambiguity doesn't matter), and can be compiled into DFAs. $\endgroup$
    – rici
    Jul 20, 2020 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.