3 ms·
We don't need to decide to apply this rule sometimes but other times that rule. When we come to an ambiguous string, we apply both rules nondeterministically. H
by yepguy 11y ago
We don't need to decide to apply this rule sometimes but other times that rule. When we come to an ambiguous string, we apply both rules nondeterministically. Here's a pseudo-grammar that I think describes both possibilities.
Statement -> Type Op Var ";"
Statement -> Var Op Var ";"
Op -> "*"
I think the disconnect here is that most lexers would insist on feeding a different token to the parser depending on whether "foo" is a Type or a Var, and choosing one or the other means the lexer might feed it bad information. The pragmatic way to implement this in a real compiler is to add some logic to the lexer so that it's working with more information than just the syntax. Theoretically though, all that really matters is that both possibilities are syntactically valid. So another way to implement it would be to pass on both possibilities, letting the parser eliminate the one that doesn't compile.
- kazinator 11y agoIndeed. There is a rule that Type generates Identifier, which can generate an example like foo. Likewise, Var generates Identifier, which generates foo. But these generations are not purely grammar rules; Type can only generate foo if there exists a declaration in the semantic space. If we regard it as purely a grammar rule, then we have a straightforward ambiguity in a context-free language. It is context-free simply because the rules are all of the form one_sym -> zero_or_more_syms. If C were parsed this way, nondeterministically, ultimately the ambiguity would be resolved by looking up the type info anyway. (The interesting possibility exists, though, that in some cases the type info could be inferred, based on how the declared identifier is used.)