Lambda the Ultimate

Could you expand on your example a little bit. Say I try to parse "0xfeL", what would be the exact output: ValueType=Long, WholePart=HexChar=f, WholePart=HexChar=e perhaps?

I'm a little bit unsure what information you are trying to recover at the end of the match as the properties / attributes that you've tagged seem to overlap.

In general though: have you considered a stack of attribute/value pairs and annotations to some of the edges in your state-machine so that when the edge is followed the attribute/value is pushed onto the stack and at the end you pop everything off to recover the merged trace?

The end goal, if I can manage to pull it off, is to write a parser generator which will parse the text and give you an object which represents the text you gave it. Similar to regular expressions, except cleaner, with expression references, recursion for rules, and an object model which maps directly to your syntax outline.

In the case of 0xfeL (0xfel, 0xFeL, 0xFel, 0xfEL, 0xfEl 0xFEl, or 0xFEL, since the '@' before 'L' means 'case insensitive'), it would give you ValueType=Long, WholePart= 'fe' and 'WholePartType'=HexChar. Since there's no means to inject what to do when you match something, when determining the numeric value of the result you would have to use the context it defines about the parse to determine its value. In essence you'd be somewhat reparsing it, but the context of how to do it would be handed to you.

The idea is: if you're going down two different parse paths, the 'names' in play can overlap. Things like WholePartType would only be necessary if two values of the same name have differing types but the same underlying result value (both would capture a string.)

Calculating the value of a number in a language is trivial, especially when you know the base you're working in.

Ideally, if you gave it the string 65.25e-7m, you'd get a Number with a ValueType=Decimal, Exponent wouldn't be null, with a Sign=Negative, Value=7, WholePart=65, WholePartType=DecimalNumber, FloatingPart=25. That's the goal, at least.

Calculating the value of a number in a language is trivial, especially when you know the base you're working in.

Ideally, if you gave it the string 65.25e-7m, ...

What's your definition of "trivial"? For most of us mere mortals, floating-point textual representation I/O was a black art until 1990 when we were shown how to do it properly by Clinger (Input), and, Steele and White (Output). See "Proceedings of the 1990 ACM Conference on Programming Language Design and Implementation" for details.

Can you point me to "Proceedings of the 1990 ACM Conference on Programming Language Design and Implementation?"

I think we're talking different things here. I merely meant that the result would be:

private static double CalcResult(string WholePart, string FloatingPart, ExponentSign ExponentSign, string ExponentValue)
{
    int state = 0;
    double result = 0;
getDoubleVal:
    string current = string.Empty;
    double curResult = 0;
    if (state == 0)
        current = WholePart;
    else if (state == 1)
        current = FloatingPart;
    else if (state == 2)
        current = ExponentValue;
    for (int i = 0, c = current.Length; i < c; i++)
        curResult += ((double)(current[(c - 1) - i] - '0')) * Math.Pow(10, state == 1 ? -(c - i) : i);
    switch (state)
    {
        case 0:
        case 1:
            state++;
            result += curResult;
            goto getDoubleVal;
        case 2:
            result *= Math.Pow(10, (ExponentSign == Program.ExponentSign.Positive ? 1 : -1) * curResult);
            break;
    }
    return result;
}

Sorry for the late reply, but I had to go to work. Did we mean different things?

See session 4 of http://www.informatik.uni-trier.de/~ley/db/conf/pldi/pldi90.html

Thanks for the reference.

I haven't done much work with floating point arithmetic, increasing the precision beyond the target data type makes sense, since in the example I gave, each step is an approximation, it would likely yield a suboptimal result.

The main focus was that hexadecimal/decimal/standard base conversions are fairly straight forward when you know the source base and your target base (10, in this case.)

I don't know enough about IEEE standard to say whether it's trivial or not. I'm going to guess not due to the fact that there's a standard behind it...?

Edit: You were correct, increasing the precision of the type used for the calculation increased the precision of the result, though I'm sure there's a better way to do this, such as encoding the results directly in the format the floating point value is stored in. I'm thinking the best method would be to serialize the bits of the floating point value directly.

Going back to your original question: you have productions in your grammar that are being used like subroutines and you were looking for a simple way to keep track of how to recombine the sub-results.

If you pick a test-case (say for a number) that hits such a sub-routine and work out the trace for the automaton - what sequence of edges do you walk across and how does it relate to the resulting value that you want to build? If you store those edges / values in a list (basically a stack that you will only push to) then how does reading them off in reverse relate to the value that you want to construct?

The basic idea is constructing the state machine like you usually would. You have an input character and each iteration of the machine determines the next state. In intermediate steps for a capture, you'd push the data for it to a buffer and once entering its final state you'd mark the subexpression as matched.

Using GraphViz has greatly helped my understanding of how the machines work. In constructing these digraphs, I've realized that certain automations can be reduced when you see an inefficiency. If, for example, you're matching a large sequence of 'modifiers' for a struct, that have a large set of valid ordered elements (say, 50+), if your concern is simply: capture what was found, and ensure it's in the proper order. Then how you get to the end state of a given set doesn't matter. So you can reduce that set much further. To help with this, I added a new modifier character on elements '$'.

Take StructDeclaration for example. It's defined like so:

StructDeclaration                         ::=
    Attributes:Attributes;?
    (
        TupleR1<Modifiers.New, "partial", "private">  |
        TupleR1<Modifiers.New, "partial", "public">   |
        TupleR1<"internal", Modifiers.New, "partial">
    ):Modifiers;?$
    "struct"
    Identifier:Name;
    ClassOrStructHeader<No>
    '{'
        StructMemberDeclaration:Members;*
    '}'                                     ;

Previously the automation for matching a struct was quite complex; however, after adding the modifier (and code to interpret the function of the modifier), it reduced quite a lot, but maintained the functional aspect.

As far as the production rules go: Presently I've constructed a set of information that denotes each path into and out of a given rule's states. So if you're on Expression, I can look and see what follows it by checking each path that entered the rule and what occurs in that production upon accepting the target rule.

My simple idea to accept left recursion is to analyze its structure: any valid left recursive rule will have a variation which is not left recursive. Write the resulted parser to check these paths first, and try the code again with the left recursion enabled. When you first parse it, you condense it onto the stack as a symbol so the look ahead stack retrieves that rule as what's 'next'.

If you find that after that symbol there's no valid entry, the parse has completed for that production. -- Suggestions on this, I currently use this in the conditions associated to #if directives Though it lacks finesse since the early version of the parser was written when my experience level was ... much less, so my options were limited when I wrote it in.

I also had an idea on constructing the production rules. Often when you're writing a parser, productions might share underlying structure, and some parse code, with conditions set to determine what's valid. Given I'm already doing path analysis, I wonder if I could allow for you to specify conditions for a given path's inclusion. An example is ProductionRules and Templates in OILexer, they share an underlying structure on the individual rules, the only difference is templates have a different set of directives that are allowed (for defining rules, adding productions to rules, throwing errors when the data presented to the template is bad, and so on.)