up vote 0 down vote favorite

I am going through the following document trying to understand a simple grammar for a basic subtraction example (page 4).

The example states that

Simple arithmetic expressions of arbitrary length built from the subtraction operator '-' and the numerals 0 and 1 can be described by the following grammar:

E = T "-" E | T
T = "0" | "1"

I understand T is the terminal symbols, but I am having a hard time understanding E. What confuses me even more is when it is stated:

Choosing the other alternative for E we might get the derivation...

E ==> "0" "-" E

How and why is an alternative to E include E? Likewise, I am having a hard time understanding how ET derives "0" or how EET derives 1.

Could someone better explain this to me? I would greatly appreciate it to move forward in the document. Maybe with a few examples would be extremely helpful.

share|cite|improve this question
  • It's recursive. – Raphael♦ Sep 24 '14 at 7:34
  • What do you mean by ET derives "0" or how EET derives 1, Where did you see that? It is not in the document you reference. By the way, this document is more parser engineering with specific techniques, than syntax and parsing science. – babou Sep 24 '14 at 10:30
  • It is not an alternative to E, but an alternative for E: E is replaced with one of the alternatives, which may contain E again. If you have at least one alternative for E which does not contain an E itself, you can always get rid of all Es eventually. And you have such an alternative here: T. – reinierpost Sep 24 '14 at 13:05
up vote 2 down vote accepted

T = "0" | "1" means that if you want a T string, 0 or 1 will do.

E = T "-" E | T means that if you want an E string, a T string followed by - followed by an E string will do, or a lone T string will do.

Thus, for example, 1 is a T string, and is thus also an E string. Hence, 1-1 is an E string since it follows the T "-" E pattern.

Note that the double quote is just a notational device to distinguish terminal symbols from non-terminal ones.

Can you go on from here?

share|cite|improve this answer
  • thanks @babou, this was definitely helpful. I think using the phrase "string" helps me better understand here. To answer the question you posed as a comment in my question, ET derives "0" or how EET derives 1 was a reference to the tree (Figure 2) on the next page in the document. I didn't quite understand the tree or how to interpret it. – gnychis Sep 24 '14 at 16:31
  • @gnychis Yes, non terminals stand for strings they can derive into, either any one of them, or the whole set of them, depending on how you want to read the grammar (though it ultimately amounts to the same). The tree structure shows how a non-terminal derives into a string. Different paths from the root lead to different parts of the derived string. – babou Sep 24 '14 at 21:15
up vote 0 down vote

All in " " included strings are called symbols.

What you now to is to e.g. match a given input using your grammar.

Is 1-0 defined in your language? Lets have a look:

You start with the rule E which is your starting symbol (usually the first rule). This rule says that 1 has to match rule T and 0 match the rule E (they are connected using - as defined in the first part). When following the rule T we actually see that the symbol 1 is right hand side (| stands for or). So lets following the rule E for 0. E is another substraction (symbol -) or just the rule T again. The rule T has the symbol 0 so it matches. This means 1-0 is defined by your grammar.

So far so good. Now what happens if you have multiple - like in 1-1-0-1. Then you need the recursion as defined in rule E to match it. Can you see it now?

share|cite|improve this answer

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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