A Parser

You should have a look at the documentation for these tools:
Lex ( Also Flex ), and Yacc ( also Bison ). They are lexer/parser generating tools, and while they may be too powerful for what you really need, the techniques used inside those tools ARE what you are looking for.

On a more abstract level - think of working through the file in two stages: stage one is lexing, stage two is parsing. During the lexing phase, all the "keywords" are reduced from their string form to a more machine-readable "token" form ( usually just an integer ID ). Parsing then combines the series of tokens into sensible forms, checking if the file is well-formed along the way.


Give me one more medicated peaceful moment.
~ (V)^|) |<é!t|-| ~
ERROR: Your beta-version of Life1.0 has expired. Please upgrade to the full version. All important social functions will be disabled from now on.

There is an EXCELLENT serie of articles on Flipcode about developing a scripting engine from scratch. I think that would give you even more than you are asking. Because all you want here is being able to assign values to variables...
hope it helps a little bit.

there was also much talking about such system in a thread on magic. Maybe Solthar did get more info about hte topic and could help you a bit.

youpla :-P

MadKeithV - Yes, I've heard about those two stages. int Andre LaMothes' book "GAme Programming in 21 days", he writes a text based game in it, but that only parses single lines. anyway, ill check it out.

I was also looking for some more technical advice. Not so abstract .

Edited by - Zipster on September 4, 2000 3:45:30 PM

You just can''t expect people to write the code you need on this page. Need to do the work yourself, based in the general theory.

Instead of just ready a few articles that doesn''t give you a deeper understanding of the problem I recommend that you read some of the "proper" in-depth litterature on the subject.

Assuming that you prefer C/C++ then a good book to start with is:

Aho, Sethi and Ullman: Compilers - Principles, Techniques and Tools. Addison-Wesley.

After reading this you can do parsing, lexing, semnatic analysis and write your own compilers and interpreters for your own languages and data formats. An essential read - with lots of practical examples.

Jacob Marner

Well, I think that basically what you do is to read in one byte at a time, and see what it is. If you run into capital letters, you know you have a keyword (as in your example, like "BEGIN DATABASE" or whatever). If you run into a quote, then you set a flag that means you are currently reading in a variable, so that when you hit the end quote you know that it is the second quote and not the first. etc.

Lots of trial and error, but it should work ok. If you look at the ANSI character codes, you should be able to use ranges of characters (like, "if( byte >= ''a'' and <= ''z'' )" etc.). That would make the job a lot simpler. Use stream I/O and ignore tabs, spaces, and ''\n'' - the endline character. The only things you need to recognize are to read in that sample text database are:

1. the phrase BEGIN DATABASE
2. the phrase END DATABASE
3. the opening {
4. a variable''s name
5. the = sign
6. a variable''s value (the stuff in quotes)
7. the ending }

You can ignore the object and the type if you want to (just to let the file-writer use it to keep track of stuff), or you can include them in your list of things to recognize.

Then you''ll have to code some sort of data structure which can hold all of these things. Use lots of map&ltstring, string> to map the names of the variables to the values, and make a Query() function that can sort through them and find a value from the name of a variable.

Just some of my notes.

Let me know how it goes!

---

- null_pointer
Sabre Multimedia

quote:

---

You just can''t expect people to write the code you need on this page. Need to do the work yourself, based in the general theory.

---

I NEVER asked anyone to write the code for me. In fact, I asked someone to explain the general theory!

Well, I did some reading in some of Andre LaMothes books, and found a good description of how to do it. There will be a lot of trial and error, but I have it down now. It should be (almost) smooth sailing. I already have a simple parser, meaning that it translates the words into integer tokens, but really doesn''t do anything with them.

=======================================
A man with no head is still a man.
A head with no man is plain freaky.

Hi,

i normally use a state machine for that. To do that i first load the complete file into memory. Then i remove all the whitespace stuff and comments; afterwards i start to parse char by char.
While parsing i am moving from one state to another. This is pretty cool since you always now that from one state you can tansit only to n other states.
What you then need is a syntax (4G Tupel contextfree grammar) which describes your language.

I often use a pattern like:

"$Returncode = @functionName(paramlist)"

.....

param := ....
paramlist := |


So if you start with an initial state:

SEARCHING_RETURNCODE_OR_FUNCTION_NAME
all you will parse for is a
returncode (delimited by a ''='') or a function name starting with
''@''.

If you have found an Returncode
your state is SEARCHING_FUNCTION_NAME

If you have found a function
your state is SERACHING_PARAM_LIST

etc.

If you are interested i can mail you a complete frame for such
an "interpreter" (VC ++ 6.0) to have a look and to use it.

cu

Peter

PS: here is a little sample what i can process.
You can easily add new commands to that thing and
also use for implementing an interpreter.


#
* Order Screens
#
@OrderScreen
(
@

@Type (InputOutputPage),
@Format(''3270 - 2''),

# Optionales SQL Statement zur Parameterbeschaffung #
$Order = @SQL(''SELECT * FROM Order''),

# Aufzaehlung aller Input Felder und deren Attribute #
@InputFieldList
(
#
* Feldname X, Y, Len, Typ DataSource
#
@Field(WKN, 1, 4, 6, Alphanumeric, Order.WKN),
@Field(Stueck, 3, 4, 6, Alphanumeric, Order.Stueck),
@Field(Preis, 5, 4, 6, Alphanumeric, Order.Preis)

),

# Aufzaehlung aller Output Felder und deren Attribute #
@OutputFieldList
(
#
* Feldname X, Y, Len, Typ DataTarget
#
@Field(WKN, 1, 4, 6, Alphanumeric, Bestand.WKN),
@Field(Stueck, 3, 4, 6, Alphanumeric, Bestand.Stueck),
@Field(PreisBezahlt, 5, 4, 6, Alphanumeric, Bestand.Preis)

)


)


@LoginScreen
(

@Type (InputPage),
@Format(''3270 - 2''),

$Login = @SQL(''SELECT Name, Password, ID FROM User''),

@InputFieldList
(
@Field(Name, 1, 4, 6, Alphanumeric, User.Name),
@Field(Password, 3, 4, 6, Alphanumeric, User.Password),
@Field(ID, 5, 4, 6, Alphanumeric, User.ID)
)

)


$MRC = @Mesh
(
me1,
$TRC = @Triangle
(
tr1,
tr2,
tr3
),
me2
)


$ARC = @A
(
$BRC = @B
(
b1,
$CRC = @C
(
c1, c2, c3
),
b3
),
a2,
a3
)

$DRC = @D(''@[1]'', BUBU. HALLO)

No offense, but you will not get the proper theory from LaMothe''s books. His book never really go in depth but just touches a lot of subjects.

The suggestion about taking one character at the time you are making a parser for so-called LL(1) languages which is only small subset of all possible languages, and the way to it is called a predicative parser. Many data formats (e.g. C++ itself) are not LL(1) languages and cannot be parsed this way.

phemmer then suggests the use of a state machine. This kind of parsing is often using in lexers such as lex because it is fast but this type of parsing can only be used to parse regular grammers (i.e. grammers for languages that can be written in EBNF-form - such as this "[I | he] [am | is] a [big*] car"). Regular grammers are even weaker than LL(1) grammer is that you not can parse nested structures.

What you need is a LALR(1) parser such as that used in YACC. With that you will be able to parse almost any language you can imagine. The parsers used for your own C++ compiler is a LALR(1) parser.

Jacob Marner

quote:

---

Original post by felonius

No offense, but you will not get the proper theory from LaMothe''s books. His book never really go in depth but just touches a lot of subjects.

The suggestion about taking one character at the time you are making a parser for so-called LL(1) languages which is only small subset of all possible languages, and the way to it is called a predicative parser. Many data formats (e.g. C++ itself) are not LL(1) languages and cannot be parsed this way.

phemmer then suggests the use of a state machine. This kind of parsing is often using in lexers such as lex because it is fast but this type of parsing can only be used to parse regular grammers (i.e. grammers for languages that can be written in EBNF-form - such as this "[I | he] [am | is] a [big*] car"). Regular grammers are even weaker than LL(1) grammer is that you not can parse nested structures.

Hi felonius,

you are absolutely right, but i did not want to bring to much
"Chomsky language type 0,1,2,3" like theory in the group, because you can still write such a thing without knowing the in depth details of grammars and automats. Since i am using a state stack inside my automat i can process recursive declarations. That means a "function" can contain a parameter which is a function and so on.

cu

Peter




What you need is a LALR(1) parser such as that used in YACC. With that you will be able to parse almost any language you can imagine. The parsers used for your own C++ compiler is a LALR(1) parser.

Jacob Marner

---

And the symbols mean...? (LL(1), LALR(1), etc.)

---

- null_pointer
Sabre Multimedia

Sorry Phemmer,

I didn''t know that you used a stack in your state machine. That changes the situation a lot. I just assumed that you used a determinative finite state machine without extra variables - as it is usually done. Sorry for that.

Jacob Marner

Quotes from "Modern Compiler Implementation in C"

quote:

---

Grammars whose predictive parsing tables contain no duplicate entries are called LL(1). This stands for Left-to-right parse, Leftmost-derivation, 1-symbol lookahead.
...
The weakness of LL(k) ( k-symbol lookahead ) parsing techniques is that they must predict which production to use, having seen only the first k tokens of the right-hand side..
A more powerful technique, LR(k) parsing, is able to postpone the decision until it has seen input tokens corresponding to the entire right-hand side of the production in question, and k tokens more beyond.
LR(k): Left-to-right parse, Rightmost Derivation, k-token lookahead.
...
LALR(1): Look-Ahead LR(1)...

---

Give me one more medicated peaceful moment.
~ (V)^|) |<é!t|-| ~
ERROR: Your beta-version of Life1.0 has expired. Please upgrade to the full version. All important social functions will be disabled from now on.

To null_pointer:

LL(1): A grammer in which you can determine what grammar production to use solely based on the next token in the input stream. The 1 says we only look 1 token ahead. The last L is for Left, because we look at the left side of each production when dermining what to choose. I have been unable to find out what the first L stands for but my guess is that it stands for Look. Does somebody else know?

LR(1): As LL(1) but we look at the full production durig parsing which makes it easier to determine what production to use. R is for Right.

LALR(1): Parsers can be quite hard (an inefficient) to make and run for LR(1) grammers, so one can use parsers for look-ahead LR (LALR) grammars which is a subset of LR(1) but with the property that parsers can be very quite efficient. All programming languages that I know of are therefore made LALR grammars. If you define a dataformat or programming/scripting language and it is not LALR (with Shift/Reduce conflicts removed, meaning that it is actually a superset of LALR - I will not get into details about this here) then you better rewrite it.

All of the above grammar describes languages that are subsets of of the languages that can be described using context free grammars. They are also a superset of the languages that can be described with regular grammars.

The book that I referred to above describes how to make (among others) LL and LALR parsers.

Jacob Marner

MadKeithV posted before me. Darn! :-)

Zipster,

Although we have spoken a lot about making parsers for you text file an alternative and easier approach is to use XML format.

XML is a HTML-like format for use for custom data. It is very useful for the kind of data that you have show in the your example database.

You can use XML editors to write your own files (they usually even do syntax checking for you) and you can use free libraries to to all the parsing in a very simple way. These libraries can also generate XML files for you based on your data. XML is portable too, if that matters to you.

I think you should try it out. On have only tried XML parser for Java, but those for C++ should be very much like it. I don''t have any names though. You must look them up yourself.

Jacob Marner

felonius:

um...yeah...I knew that... (j/k)

So, what''s a production? No, better just tell me something:

"int x = int(5) * min(y, z);"

What will a LALR parser do with that sample statement (assuming it''s been broken down into tokens, etc.), and what would a LL(1) parser do? int and min are keywords (in the example), the "()" indicate a function call, ''='' and ''*'' are operators, x, y, and z are identifiers, and '';'' indicates the end of the current grammar statement (a production?). If you could just give me a concept or something, I could probably write a very basic LALR parser (I have good experience with C++).

(I''d go out and get the book, but I''m broke... )

---

- null_pointer
Sabre Multimedia

null_pointer I see where this is leading...I can''t explain all the book in a few postings and I canøt just explain some terms without using other terms. It is hard knowing what you (or other people) already know. Please read the book that I recommended (called the Dragon-book) or the one MadKeithV spoke about "modern compiler implementation in C" - also a good book if it is as good as its cousin "modern compiler implementation in ML", which I have also read (Called the Tiger-book).

A production is a grammar rule, so if I wanted to make a grammar for expressions it could be something like (choosing a notation for the productions at random):

Expression := Term ''+'' Expression
Expression := Term
Term := Factor ''*'' Term
Term := Factor
Factor := ''('' Expression '')''
Factor := 1
Factor := 2
...
Factor := 0

Each line above is a production. There exists production shortcuts so the two first lines may be written as
Expression := Term [''+'' Expression]

Using this grammar the following line would be legal:

5*(6+7)
while this would not
5**)(

Jacob Marner

By the way, you just DON''T write a simple LALR(1) parser. That is quite complex to do, so I will NOT explain it here. Read a book!

Jacob Marner

quote:

---

Original post by felonius

Zipster,

Although we have spoken a lot about making parsers for you text file an alternative and easier approach is to use XML format.

XML is a HTML-like format for use for custom data. It is very useful for the kind of data that you have show in the your example database.

You can use XML editors to write your own files (they usually even do syntax checking for you) and you can use free libraries to to all the parsing in a very simple way. These libraries can also generate XML files for you based on your data. XML is portable too, if that matters to you.

I think you should try it out. On have only tried XML parser for Java, but those for C++ should be very much like it. I don''t have any names though. You must look them up yourself.

Jacob Marner

---

Hi Jacob,

pretty cool idea using XML; we are using that XML stuff at the moment with a C++ library for a very large project and it works fast and fine. Another idea would be to use a TCL interpreter inside your application. TCL is very flexibel and even the built in commands can be modified. I have seen a lot of things which were done using TCL inside an app and it worked pretty fine.

cu

Peter