Solved

PROGRAM statement conversion to BNF?

Posted on 2003-10-29
26
401 Views
Last Modified: 2010-04-16
What would be the conversion of the following Pascal PROGRAM statement into BNF:

-------------        +------------+                      +-------------+
(PROGRAM) -->  | Identifier |  -->  "("  -+->  | File Name |  -+-> ")" --> ";"
-------------        +------------+               ^     +-------------+   |
                                                           |                            |
                                                           +---------","----------+          


File Name
               ---------
------+--> (INPUT)  ----------------+----->
        |     ----------                     ^
        |                                       |
        |      ------------                  |
        +--> (OUTPUT) ------------>+
       |       ------------                  |
       |                                        |
       |      +-----------+                |
       +--> | Identifier|  ---------->|
              +-----------+
0
Comment
Question by:GunNam
  • 13
  • 13
26 Comments
 
LVL 11

Expert Comment

by:bcladd
ID: 9641316
This sure soundsl like homework. (Intro programming languages, perhaps?)

I am willing to help a little:

FileName ::= (INPUT) | (OUTPUT) | Identifier

(note that this may be considered EBNF; I can never remember whether in-line alternation is BNF or E-).

Hope this helps,  -bcl
0
 

Author Comment

by:GunNam
ID: 9641573
is BNF basically context free grammer?
0
 

Author Comment

by:GunNam
ID: 9641600
in the case of "PROGRAM" would converting this diagram into BNF require breaking PROGRAM down into A-Z?
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9641639
BNF (Backus-Naur Form)  (named for John Backus and Peter Naur (and, just to show off, I did that from memory before looking it up to make sure I had their first names right)) is a way of expressing context free grammars. In traditional BNF (I went and looked it up), you're limited to using simple productions (no alternation so my answer above is EBNF (E for extended)) without metalevel parentheses or Kleene stars.

So to do what I said, you would need three alternate rules:

FileName ::= (INPUT)
FileName ::= (OUTPUT)
FileName ::= Identifier

The tricky part is expressing continuations. Consider a list of items, call the non-terminal ItemList and assume there is another rule for Item. No empty lists are permitted. The following BNF should be able to handle ItemList:

ItemList ::= Item
ItemList ::= Item ItemList

Hope this helps. If you need book references, let me know.

-bcl
0
 

Author Comment

by:GunNam
ID: 9641731
could I define "PROGRAM" as an Identifier with PROGRAM since those are the exact characters I'm looking for?
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9641776
Your question about A-Z is a good one. I assumed from the way the diagram was drawn that you have a lexical analyzer that provides tokens (the parentheses around the keywords, for example, says to me that your input consists of a sequence of keywords, identifiers, and punctuation symbols. I could be wrong and you should carefully read the assignment.

-bcl
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9641819
As I said, your lexical analyzer should read and identifier and, before returning the token, check whether or not the ID represents a keyword (for languages that have reserved keywords). It should then change the type of the token returned to be appropriate to the keyword.

That would mean the following input:

PROGRAM Flunky (INPUT, MyFile);

should be lexically analyzed into the following sequence of tokens:

Keyword: PROGRAM
Identifier: Flunky
LeftParen
Keyword: INPUT (technically I think this is actually a reserved identifier but I am going to pretend it is a keyword)
Comma
Identifier: MyFile
RightParen
SemiColon

Then your parser (implementation of the BNF accepter, parse-tree builder, or direct code generator) would be able to match the sequence against the given BNF.

-bcl
0
 

Author Comment

by:GunNam
ID: 9642040
Alright, I looked back at some stuff I wanted to forget... the dreaded compilers class.  It looks as though what I'm looking for is the specification of the lexical analyzer... well similar to it anyway.

tell me what you think:
(tokens)
<(PROGRAM)> ::= <"(PROGRAM)">
<File Name> ::= <"(INPUT)">
<File Name> ::= <"(OUTPUT)">
<OpenParens> ::= <"(">
<CloseParens> ::= <")">
<semicolon> ::= <";">
<comma> ::= <",">
** Identifier is self explanatory in this instance **


<(PROGRAM)>:=<Identifier> <OpenParens> {<File Name>}* <comma> <CloseParens><semicolon>

I'm having a bit of a problem on the looping of the comma.  As it looks right now:
It would read that (PROGRAM) is an <Identifer>followed by "(" followed by ONE or more <File Name> followed by a <comma> followed by a ")" and ";"
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9642100
Okay: In the lexical analyzer you don't want the () around the names; the word (case-insensitive for Pascal) "program" is the token of type PROGRAM.

Look carefully at your EBNF (you're using *) for the PROGRAM statement. By your definition you have any number of file names  followed by a single comma (comma is NOT controlled by any looping or alternation) followed by a closing paren. Probably NOT what you want.

You CAN uses more than one rule for PROGRAM (to handle 0 and more than 0). Or you can work on what goes inside the parentheses.

-bcl
0
 

Author Comment

by:GunNam
ID: 9642128
Using what you wrote about keywords (since this pertains to the Pascal Program statement).  (* [ ] signifies zero or more *)


<PROGRAM> ::= <Identifier><OpenParens>[<File Name>][<comm>]<CloseParens><semicolon>
                                                       
<KEYWORD> ::= <PROGRAM> | <INPUT> | <OUTPUT>
<File Name> ::= <KEYWORD> | <Identifier>

0
 

Author Comment

by:GunNam
ID: 9642148
I'm not sure how to make sure to include a <comma> if there is more than one File Name included.... and then to make sure it doesn't end up before the <CloseParens>... or does it matter since I can designate it to be zero or more?
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9642170
Close. Your statement recognizes the following

Program(A B C ,,,,,,,,,,);

There is no relationship between the number of filenames and the number of commas. (the grammar is context-free after all).

Consiider the following to recognize a sum of integers:

Sum ::= Int ['+' Int]*

Using []* for zero or more repetitions. Typically [] alone is used for "optional" elements (0 or 1 repetitions).

-bcl
0
 

Author Comment

by:GunNam
ID: 9642390
<PROGRAM>::=<Identifier><OpenParens>[comma]*[<File Name>]* <CloseParens><semicolon>

??  am I getting close?  I about to try something with the definition of <File Name>
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 11

Expert Comment

by:bcladd
ID: 9642452
Stop. Take a deep breath. Let's look at an english definition of the problem (or go back to the picture):

"PROGRAM" followed by an identifier, followed by parentheses containing one or more file names separated by commas  and followed by a semicolon.

Okay. Notice that there is a relationship between the file names and the commas. In fact, after the first file name, any additional file name must have a comma before it (notice: by putting it before we get rid of the comma before close paren problem). That is we need to apply the star to a group of two tokens, the comma AND the following file name. Similar to the plus sign and the following int in my previous example.

FileName [ comma FileName]*

One is required, additional ones must be separated from the previous list by a comma.

-bcl
0
 

Author Comment

by:GunNam
ID: 9642526
I just took a deep breath of my cigarette =)

<PROGRAM>::=<Identifier><OpenParens>[<comma><File Name>]* <CloseParens><semicolon>

So looking at this... (to me) would say:
PROGRAM followed by an Identifier followed by a ( followed by Zero or more comma & File Name followed by ) followed by a semicolon.

So... by putting the comma & Filename together, it rids the fact that a bunch of consecutive commas can be written.  For a comma to be written now, it must be followed by a File Name.  AND because comma & File Name is now one entity, the comma MUST be there if a File Name exists.  But doesn't this mean that I can start the File Name list WITH a comma?  I haven't tried it, but I wonder if it produces an error on my compiler...
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9642580
Yes, it will permit a starting comma.

Look at the example I gave above. To avoid the problem I put a FileName BEFORE the grouped comma and FileName. Requires at least one FileName to match AND makes sure that any commas that appear are between two FileNames (where they belong).

-bcl
0
 

Author Comment

by:GunNam
ID: 9642632
I didn't even notice your example... so it looks like this is it?

<PROGRAM>::=<Identifier><OpenParens><File name>[<comma><File Name>]* <CloseParens><semicolon>

In the lexical analyzer of an actual compiler (not the diagram above), it would probably put [<File Name>][<comma><File Name>]* right?  Since a File Name is not required between the parentheses?
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9642692
Actually it is

[ FileName [comma FileName]* ]

The difference is that with yours the first FileName is optional so we COULD skip it and start the list with a parentheses.

Also, this is PROBABLY part of the parser. Typically lexical analyzers work at a very simple level (say regular expressions; can be compared to the rules for spelling words that work with letters) and parsers work at a higher, more complex level (say context-free grammars; can be compared to the rules of grammar that work with words). This division is artificial since any regular expression can be expressed with a context-free grammar (a limited CFG at that) but it is made for ease of implementation of the parser.

-bcl
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9642724
Doh-

The difference is that with yours the first FileName is optional so we COULD skip it and start the list with a _comma_.

Proof reading helps.

-bcl
0
 

Author Comment

by:GunNam
ID: 9642725
Final GunNam Release?

<PROGRAM>::=<Identifier><OpenParens>[<File name>[<comma><File Name>]*] <CloseParens><semicolon>
0
 
LVL 11

Accepted Solution

by:
bcladd earned 125 total points
ID: 9642772
Looks good to me. It accepts a list of 0 or more comma separated file names between the parentheses.

Actually, depending on notation I think it is just a little off:

::= is used to separate a non-terminal from the replacement for that non-terminal. So you need:

<ProgramStmt> ::= <Program> <Identifier><OpenParens>[<File name>[<comma><File Name>]*] <CloseParens><semicolon>

Where <Program> is the program token.

-bcl
0
 

Author Comment

by:GunNam
ID: 9642815
Thanks bcl, it's like you were right here tutoring me with your rapid responses... I'm gonna up the points for you.  

Look for some of my other questions =)
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9642976
Glad I could help. This is one of my favorite classes to teach.

-bcl
0
 

Author Comment

by:GunNam
ID: 9642995
Is this what teachers do on their free time?
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9643129
I am on leave this year to write programs for a living and when I have time I still like to teach. So yes, this is what some teachers do with their free time.

-bcl
0
 

Author Comment

by:GunNam
ID: 9643144
Well good luck to you, and thank you very much for helping out!
0

Featured Post

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Is your Office 365 signature not working the way you want it to? Are signature updates taking up too much of your time? Let's run through the most common problems that an IT administrator can encounter when dealing with Office 365 email signatures.
In this article, I will show you HOW TO: Install VMware Tools for Windows on a VMware Windows virtual machine on a VMware vSphere Hypervisor 6.5 (ESXi 6.5) Host Server, using the VMware Host Client. The virtual machine has Windows Server 2016 instal…
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now