🔒 Locked

Arrays/indexing in recursive descent parser

Started by Kylotan Sep 28, 2005 at 9:22 AM 9 replies 3.3k views

Original Post

Sep 28, 2005 at 9:22 AM

I have a simple recursive descent parser which parses and interprets most expressions okay. This includes manipulation of variables, which are stored in a global symbol table (ie. an std::map of name -> value pairs). What I need to do is extend this so that I can support (a) arrays/collections of variables, and (b) composite variables, like structures/classes in C/C++. The general plan is to treat array indexing and member resolution in the same way, so that obj.abc is equivalent to obj["abc"]. From memory I believe &#106avascript and some other languages work this way, and it should simplify the code. I am also hoping that I can effectively get namespaces as a side-effect of this. Being very rusty at this sort of thing, my first grammar attempt looks like this:


variable --> varName IndexExpr | varName
IndexExpr --> dotIndexExpr | bracketIndexExpr
dotIndexExpr --> '.' variable
bracketIndexExpr --> '[' expression ']'

Assume expression and varName are defined already and are reasonable. For instance, expression includes constants and variables. I can see the above doesn't allow for var1[20].var2, but my idea to fix it would require a lot more rules, which I'm sure I don't actually need. Any suggestions? I'm sure that I just can't see the wood for the trees here. Also, any hints on how to implement this generally, especially with regard to the 'every object has its own symbol table' concept (or viewed conversely, 'the global namespace is just an unnamed object' concept), and handling this at arbitrary recursion depths. Any insights from anyone who's done this, especially in the context of an interpreter rather than a compiler, would be welcome.

kSquared

Sep 28, 2005 at 10:10 AM

Quote:
I can see the above doesn't allow for var1[20].var2, but my idea to fix it would require a lot more rules, which I'm sure I don't actually need. Any suggestions? I'm sure that I just can't see the wood for the trees here.

Try perusing C#'s grammar. This nicely hyperlinked version should give you a kick-start.

What about something like this:

id --> {set of valid identifiers in your language}exprList --> expr exprListexpr --> id | expr access | id access | {set of valid expressions in your language}access --> '[' expr ']' | '.' expr

Something like a["b" + 5].c is now tokenized to:

expr1 (a["b" + 5].c) --> expr2 (a["b" + 5]) access1 (.c)expr2 (a["b" + 5]) --> id1 (a) access2 (["b" + 5])access2 --> '[' expr3 ("b" + 5) ']'expr3 ("b" + 5) --> baseExpr ("b" + 5)access1 (.c) --> '.' expr4 (c)expr4 (c) --> id2 (c)

So the tree is:

[edit: Argh, the forum is eating my backslashes. I'll post a picture instead.]

Kylotan

Sep 28, 2005 at 10:27 AM

Ok, that's a bit of help. One problem is, I don't build a syntax tree - it's implicit, and I execute as I go along. In that context, every part of the grammar has some associated action and return value. For example, the 'addExpression' would parse 2 parameters, add them together, and return the total to the caller. Given the grammar suggested above, how do I handle 'expr access' and 'id access'? I suppose they should both resolve to a reference to a variable somewhere. In fact, I suppose it is just really 3 ways of saying the same thing, so perhaps it's not as complex as it looks.

Also, I can't have 'expr access' in my expr rule as it's left-recursive. (I have looked up how to fix this, and although I found the answer, it is quite literally greek to me.)

Enigma

Sep 28, 2005 at 10:38 AM

Apologies if my wording is off, it's been a few years since I've dealt with this kind of stuff.

If you have a left recursive rule, i.e.:
expression -> (some sequence) | expression (some other sequences)
Then any expansion will eventually have to follow the production:
expression -> (some sequence)
otherwise it never terminates.
So you can break the expression down into a pair of expressions:
expression1 -> (some sequence) expression2 expression2 -> epsilon | (some other sequence) expression2.
Now an input which would have matched just (somes sequence) to expression matches (some sequence) to expression1 and epsilon to expression2. An input which would have left recursively matched (some sequence)(some other sequence) now matches (some sequence) to expression1, (some other sequence) to expression2 and then epsilon to expression2 (again).

EDIT: I'll be more helpful and try to show how you can actually apply this to the grammer kSquared posted (what's the betting I mess this up?):

expr --> id | expr access | id access | {set of valid expressions in your language}
becomes
expr --> id expr2 | {set of valid expressions in your language} expr2 expr2 --> epsilon | access expr2

Hope that helps,

Enigma

Zahlman

Sep 28, 2005 at 10:41 AM

Quote:
Original post by Kylotan
The general plan is to treat array indexing and member resolution in the same way, so that obj.abc is equivalent to obj["abc"]. From memory I believe &#106avascript and some other languages work this way, and it should simplify the code. I am also hoping that I can effectively get namespaces as a side-effect of this.

Just wanted to throw my support behind this idea. Personally I was planning to support just the [] syntax (though it will probably be literally years before I ever get around to doing this sort of thing), and have support for 'symbols' for members - such that obj[abc] is equivalent to obj[x], where x contains the string "abc", except that the former is resolved at compile-time. OTOH, maybe that's not such a good idea, now that I stare at it; it could be a naming conflict nightmare for users :s

Quote:
Being very rusty at this sort of thing, my first grammar attempt looks like this:
variable --> varName IndexExpr | varNameIndexExpr --> dotIndexExpr | bracketIndexExprdotIndexExpr --> '.' variablebracketIndexExpr --> '[' expression ']'
Assume expression and varName are defined already and are reasonable. For instance, expression includes constants and variables.

I can see the above doesn't allow for var1[20].var2, but my idea to fix it would require a lot more rules, which I'm sure I don't actually need. Any suggestions? I'm sure that I just can't see the wood for the trees here.

Why not just:

variable --> varName (IndexExpr)*IndexExpr --> dotIndexExpr | bracketIndexExprdotIndexExpr --> '.' varNamebracketIndexExpr --> '[' expression ']'

Quote:
Also, any hints on how to implement this generally, especially with regard to the 'every object has its own symbol table' concept (or viewed conversely, 'the global namespace is just an unnamed object' concept), and handling this at arbitrary recursion depths. Any insights from anyone who's done this, especially in the context of an interpreter rather than a compiler, would be welcome.

I don't really have the experience, but I would suggest talking to the Python guys, since in Python the global namespace *is* just an unnamed object (it's a dict, and you get at it through a function call 'globals()' rather than a simple name). I'm pretty sure they know a thing or two about interpreters vs compilers too ;)

Kylotan

Sep 28, 2005 at 10:52 AM

Quote:

Original post by Zahlman
Why not just:

variable --> varName (IndexExpr)*IndexExpr --> dotIndexExpr | bracketIndexExprdotIndexExpr --> '.' varNamebracketIndexExpr --> '[' expression ']'

Hmm, yeah... an iterative attempt might work here. I guess the parsing pseudocode for the 'variable' rule would be:

currentSymbol = ParseVarName(context=globals)do:    indexValue = ParseIndexExpr(context=currentSymbol)    if indexExpr is None:        break    else:        currentSymbol = currentSymbol.LookUp(indexValue)While 1Return valueOf(currentSymbol)

Quote:
I don't really have the experience, but I would suggest talking to the Python guys, since in Python the global namespace *is* just an unnamed object (it's a dict, and you get at it through a function call 'globals()' rather than a simple name). I'm pretty sure they know a thing or two about interpreters vs compilers too ;)

Python compiles to bytecode though, so they can defer the execution until later. I have to do it as I go along.

ToohrVyk

Sep 28, 2005 at 10:53 AM

I have toyed with similar question recently. At the implementation level, all objects in my interpreter were either a context (that is, a map) or a base variable (whatever ints your boat), with the "universe" being a context. The interpreter also had a "current" registry, which was initially set to "universe".

My grammar contained an "object" type that was defined by rules:

object -> path end  path -> variable         | variable '.' path             (i)

Upon encountering a variable node, the interpreter looked into the "current" registry (which was assumed to be a context), found the variable name in that context, and put the associated object in the "current" registry. In the case of rule (i), variable was explored before path was. Upon reaching a end node, the interpreter returned the contents of the "current" registry as the contents of the object node, and placed "universe" back in the "current" registry (*)

To also account for foo[bar] syntax, and since foo[bar] works in the same way as foo.bar, you could change the rule to take into account :

path -> variable | variable '.' path       | variable subscript              (ii)subscript -> '[' variable ']'            | '[' variable ']' subscript (ii)           | '[' variable ']' '.' path  (ii)

With rules (ii) ensuring that variable is always explored before path or subscript.

(*) Everything occured by reference, so it was a simple matter to say, for instance, if "foo" did not exist in the universe, that foo.bar = 1; (thus initializing both a "foo" object in the universe, and the "bar" member of "foo" to 1).

ToohrVyk

Sep 28, 2005 at 11:19 AM

Or, more simply I guess,

object -> path endpath -> index ( ε | '.' path )index -> variable ( ε | subscript )subscript -> '[' variable ']' ( ε | subscript )

Kylotan

Sep 29, 2005 at 5:00 AM

What does the ε mean in this context?

ToohrVyk

Sep 29, 2005 at 5:17 AM

Nothing

A -> B ( ε | C )

is shorthand for

A -> B | BC

Kylotan

Sep 29, 2005 at 5:29 AM

Ok, that's what I thought. I think I can just replace that with an optional token like so:

object -> path end
path -> index ['.' path]
index -> variable [subscript]
subscript -> '[' variable ']' [subscript]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.