Anyone a parser expert?

[kedaman]

If I have to eliminate left recursion then wouldn't all operators become right associative? How do i get around this?

[jim mcnamara]

If you perform full recursive descent parsing - to the level of unary operators, as you 'back out' you do not lose left or right associative properties.

If you are working with natural language, forget it. No descent parser will ever work correctly, because the rules change on the fly as a function of antecedence and hermaneutic analysis.

What the heck are you doing? Writing another compiler?

[kedaman]

i'm basically writing a compiler that compiles its own rules, and yes i'm thinking about using it for natural languages as well.
I need to preserve the associative properties, if I use full recursive descent parsing, how does this affect parsing of natural languages?

[kedaman]

Say If I have these rules
A -> A + i
A -> i
where i can be any numeric, and the parser finds 1*2
How do you prevent the infinite recursion, it would apply A -> A + i wouldn't it? I want it to die and say that the expression cannot be parsed.

[CornedBee]

Something I've just noticed. In what way would A + i fit into the expression 2*3?

[kedaman]

well i shouldn't have said apply, I have a parser tree that looks like this:
A
|_(A)
|...|_+
|.......|_i
|_i
(A) is expanded with A here.

[CornedBee]

Oh, so it's not that you can't parse the source, but that your tree would blow up to infinity?

Well, isn't that the same as "self-referencing statements are not statements"? I remember a discussion somewhere

Anyway, you must make sure that the A inside the definition of A isn't expanded but is instead a reference.

[kedaman]

it is. Left recursion isn't suppose to work in regular top-down parsers, but how i'm going to avoid it with a full-backup recursive descent parser is still a mystery to me

[jim mcnamara]

You said yes to natural language. That means no to a full descent parser of any kind unless:

You have a parser that maintains a state table, and a key table

From my class notes on this stuff from 20+ years ago:

A Table-Driven Finite-State Parser routine is a general-
purpose, table-driven parser implemented as a finite-state
automaton. It parses a string and returns a message
indicating whether or not the input string is parseable -
ie., valid under the given rule set.

You need finite states & keys to be able to:
1. generate your own parsing rules ie., key table additions.
2. implement parsing natural language

In other words, run the automaton first, then parse based on the state-table. A two pass parse. (sorry for the alliteration)

The key table 'remembers' the antecedents for you. The state table allows you to navigate. You can use these in phase II.

[kedaman]

The key table 'remembers' the antecedents for you. The state table allows you to navigate. You can use these in phase II.

I'm not going to implement support for antecedents or anything that is even close to natural languages yet. Besides this should not be a concern for the parser, but will be implemented on a higher level. When the parser compiles the program, it transform the expression as each rule is a function, supplied by the user, thus you could pretty much do anything in a natural language.

What i need now is support for right/left associative expressions.. How do i go avoiding the recursion problem?