New answers tagged

0

Eventually you will end up with having to choose between $S'\to\epsilon$ and $S'\to eS$. The grammar says that's a conflict. But can't we deduce which is correct? What if we choose $S\to\epsilon$? Will we ever be able to match the e?


4

There is a simple relation between the two problems, but it goes in only one side: if you can parse, then you can recognize. Indeed, if you run the parser and it outputs failure, then the input is not in the language; if the parser produces a parse tree, the input is in the language. Note, however, that a parser and a recognizer are not only solving ...


6

The particular grammar formalism used in the grammar you cite is defined in Appendix A of that document, which includes in section A.3, a precise definition: A grammar production may specify that certain expansions are not permitted by using the phrase “but not” and then indicating the expansions to be excluded. That phrasing is certainly not unique to ...


9

In the case of regular languages (and in your examples, we're just talking about character classes, which are an especially simple form of regular language), they are closed under set difference. Not only that, but unlike (say) Thompson's method, Brzozowski's method for constructing DFAs can be easily extended to handle the set difference operator. I'm ...


11

For context-free grammars (I guess your question concerns this type of formal grammars), it would be not only painful, but also impossible in general. Suppose we have an algorithm that provides such "expansion" and yields a new grammar without $\text{but not }$occurrences. Then we can take two arbitrary context-free languages $L, L'$ with start nonterminals ...


0

If you naively generate a parse tree from $$\begin{align}T\to& FT'\\ T'\to& *FT' \\ \mid&\; /FT' \\ \mid&\; \epsilon\\ \end{align}$$ then you're going to end up with something like this: T / \ / \ / \ F T' | /|\ 6 / | \ / | \ * F T' | /|...


Top 50 recent answers are included