BNF stuff... (1 Viewer)

[Seraph]

Hi everyone we've just started BNF and EBNF syntax at school (geez my teacher jumps around the syllabus alot) , we briefly touched on it but im having some difficulty with it

Okay say i want to define a word say... the word "hey"

i know to define i would have to use

:: =
ive done this so far

LLetter :: = a|b..|z
Uletter :: = A|B|.|Z
Letter ::= < Lletter > | < Uletter >
So ive defined letters individually , but then now how do i define the actual word?
Im not sure i really understand these terminal and non-terminal things very well
This is what i think they are..
Non-terminals are already defined elsewhere like Letter ::= < Lletter > | < Uletter >
And terminals... um im not sure are they like digits or characters individually... like A-Z or 0-9

Thanks

 

[Fosweb]

First a summary of the syntax, which is different in BNF and EBNF.

BNF: The OLD one...
(Has no syntax for repition. This is done recursively.)

1. Defining: ::=
2. Non-Terminal < >
3. Terminal eg a|b|c....
4. Decision: | (Pipe)

EBNF: The NEW one (EXTENDED BNF)
(Has cooler features

1-4 Same as BNF
5. Grouping: ( ) Used to group items in an item. Particularly useful for grouping a decision inside a decision.
6. Repition: {} (Repeat the contents 0 or more times - MUST be included at least once IF THIS OPTION IS CHOSEN)
7. Optional: [] The contents are optional.


Now to your problem:
Lets simplify and take out upper/lower case for this example, just to show how repetition works:

Using BNF (which has NO syntax for repetition):

letter ::= a|b|...|z
word ::= < letter >|< letter >< word >

So what this is saying is that to repeat something, you iterate (recurrance) by including that something in the actual option also.

So in this example, when defining a 'word', there are two cases:

1. You could choose to either take A (ONE) letter, or
2. a letter followed by 'word' again, which can take one of two cases: 1 or 2.

Can you see how this keeps continuing until option 1 is chosen, and then the 'word' would end? That is how repitition is done in BNF.

EBNF has built in syntax for repition, so defining a word in EBNF is much simpler.

With the same example again, cases ignored:

letter = a|b|...|z
word = < letter >|{< letter >}

Now, the {} braces indicate repition of zero or more times. To repeat a letter, and thus make a word, the option after the pipe is chosen, and any number of letters can be included. No recurrance/iteration required.

HTH.

EDIT: Stupid < > things think its html still... I thought they turned off html on this forum? Grr.

 

[Seraph]

ahh thx fosweb ... but
Hang on okay im sort of understand for the BNF syntax ( i havent looked at EBNF yet , i just wanna get this right first)

Okay so basically its a loop right?
and to define the < word > each time it loops to spell out the word in a sense right??
BUt i dont understand why would u take the word follow by a letter...?( < letter > < word > ) what does that do???

i understand when u get to the second last letter of the word that you will obviously take just the < letter > but ... the other part....

 

[Fosweb]

You can only 'define' word once. And then you put down a set of rules for allowable syntax for that defined word.

Assume a 'word' can have ANY number of letters.

If you want to get any number of letters, you have to have a way of repeating what you already have, and adding on to the end of this to get the required number of letters. The adding on bit is done by repeating the name of what you are adding to in one of the decisions.
That is why you include < letter > < word > as one of the choices in your decision (the |).
It can be either first, or second, but to repeat, you MUST recurse. (Recurse means: what follows relies on what came before it)

Break it down into single steps.

To get the word 'hello', using word ::= < letter > | < letter > < word >, you need to repeat letters.

1. Choose < letter > < word > option, where letter = h. This then calls the 'word' again, so you get another decision.
2. Choose < letter > < word > option again, so you have h already. Now because you choose the option with < letter > < word > you have to add a letter, then add a 'word'.
So you add an e.
Now a 'word' is either a letter, or a letter followed by a 'word'.
So because you still have to add more letters, you choose < letter > < word > again.
3. You have he, this time you add 'l' and then add another 'word', which is again either a letter or a letter followed by a word.
4. You have hel, so same as above.
5. This time you already have 'hell', so you only need one more letter, so you choose the < letter > option, as you dont need to add another 'word' onto the end.
Viola.

I think once you get over the confusion of using the identifier 'word' you would be ok.
By saying that this is a 'word' that you are defining, implies that there must be multiple letters...
A 'word' must be thought of as:
1. A single letter: < letter > or
2. A letter followed by another 'word': < letter > < word >

Sorry, this is all gettign too confusing. When I have a little more time, I will think of a less confusing way to explain.

EBNF is much easier, you will be pleased.

 

[Seraph]

okay i think i understand

so the <word> means the loop as it goes along so for the word hello it would go like <h> then <he> <hel> <hell> until finally u would use just the <letter> to get o
??
and if this Is the case do i actually have to write each step(like you did above to get each letter) if im defining a certain word??

Oh also is the < letter > enclosed as a non-terminal symbol because i defined it as letter ::= ULetter|LLetter

Because usually arent the individual letters terminal symbols..?

 

[Fosweb]

so the means the loop as it goes along so for the word hello it would go like then until finally u would use just the to get o??

??? Yeah whilever you choose the < letter > < word > option, you will have to add another word after the letter you jus tadded, so you will have to add at least two letters. To end the loop, simply choose the < letter > option.

and if this Is the case do i actually have to write each step(like you did above to get each letter) if im defining a certain word??

No. You dont write the steps, you write the rules that allow these steps to occur.
So word ::= < letter > | < letter > < word > is a rule that lets these steps occur.

In the exam, my guess is you will have a multi-choice question, with a number of rules above some options. The question will say: which of these is accaptable when following the rules above.

So what you will usually have to do with BNF/EBNF questions is work backwards, from a set of characters, and work out which ones fit the rules. You do _this_ step-by-step.

There are some of these questions in each year's HSC exams that you should look at (in the M.C. section)

 

[Seraph]

Hmmm.... okay hang on one thing..


word :: = < letter > | < letter >< word >

Right??
so how come you cant take just the < letter > option at the start? And then afterwards use < letter > < word > to build the word...????

because when u use < letter > it takes an individual letter right? and all you need is an individual letter to actually start the word????

sorry i can accept exactly waht you said but if i dont get this very clear then these questions will pop-up in my mind all the time and ill never understand this properly


And btw thx for all the help hehe

 

[felix_js]

one letter words won't be possible if its just <letter><word>

 

[juventino]

I am so lost, when it comes to Bnf..

 

[Inspectah Deck]

so how come you cant take just the < letter > option at the start? And then afterwards use < letter > < word > to build the word...????

because when u use < letter > it takes an individual letter right? and all you need is an individual letter to actually start the word????

OK you cant just use < letter >, as this wouldnt let you repeat it ... let me explain a little better ok ... Think of word as a loop, and when you pick < letter > only the loop ends and hence you are left with one letter , however , when you pick < letter > < word > you get the letter BUT ' word ' is repeated again (word is defined as " word ::= < letter > | < letter > < word > ") and seeing as word is in the variable - we repeat it ... i dont know if this clears it up or not but i tried my best

 

[Winston]

Seraph, perhaps you should think BNF/EBNF in terms of how you define a variable in VB for example:

Dim <varName> as <varType>

And i wouldn't worry too much on this, primarily because BNF/EBNF is in Multiple Choice Questions mainly, and you should probably work on how to answer those questions rather than making sure you know how to construct one, but, it's still good to understand them, who knows what BOS might do. It would also be good to know some Adv/DisAdv between BNF and EBNF.