Parser in JavaScript

• Download mparser2-2.zip - 127.2 KB

Moony Parser 1.0
    - shift-reduce algorithm implemented

Moony Parser 2.0
    - implemented Earley parsing algorithm 

Moony Parser 2.1
    - bug fixes

Moony Parser 2.2
    - implemented "@AnyCharacter" variable
    - implemented substraction operator "\"
    - building grammar with javascript functions is marked obsolete. Preferred
      method is passing grammar string to compile function
    - changed returned parsed tree internal structure for memory and performance
      improvements
    - fixed recursive function call stack overflow error for big texts. Only
      memory is a limit now
    - cool grammar tester environment included in download bundle

1. Introduction

Date (
    Day {@Number},
    "/",
    Month {@Number},
    "/",
    Year {@Number}
)

          Date
           |
  +---+----+----+---+
  |   |    |    |   |
 Day "/" Month "/" Year
  |        |        |
"20"     "10"     "2013"

2. About Moony Parser

3. Moony Grammar

Person (
    Name {@Word},
    @WhiteSpace,
    Surname {@Word}
)

Vehicle {"car" | "ship" | "plane"}

@CR
@LF
@Blank
@WhiteSpace
@AnyCharacter
@Number
@Word
@Variable
@String
@RegExp
@Null 

Person (
    Name {@Word},
    Next {(@WhiteSpace, @Person) | @Null}
)

VariableDeclaration (
    Type {
        "string" |
        'int' |
        "decimal"
    },
    @WhiteSpace,
    Name {@Variable},
    EOL {';'}
)

AnyCaseWords {
    /[a-z]+/i,
    Next {(@WhiteSpace, @AnyCaseWords) | "!"}
}

4. Keyword “abstract”

AbstractTest {
    abstract Str {"parse me there, not here"} |
    Test1 ("now ", @AbstractTest.Str) |
    Test2 ("again ", @AbstractTest.Str)
}

5. Left recursion

Sum {
    Fact {
        Exp (
            {@WhiteSpace | @Null},
            {'-' | @Null},
            Value {
                Num {@Number} |
                Var {@Variable} |
                Bra (Left {'('}, In {@Sum}, Right {')'})
            },
            {@WhiteSpace | @Null}
        ) |
        MulDiv (Left {@Fact}, In {'*' | '/'}, Right {@Exp})
    } |
    AddSub (Left {@Sum}, In {'+' | '-'}, Right {@Fact})
}

6. Substractions

Str (
    '"',
    Value (
        Char {@AnyCharacter} \ '"',
        Next {@Value | @Null}
    ),
    '"'
)

7. Programming interface

// this is synchronous call to compiler and parser
var rules = parser.compileSync (grammarString);
if (rules.errors.length === 0) {
    var tree = parser.parseSync (rules.compiled, stringToParse);
    if (tree.errors.length === 0) {
        // to do something with tree.parsed
    } else {
        alert ("Text error count: " + tree.errors.length);
    }
} else {
    alert ("Grammar error count: " + rules.errors.length);
}

// this is asynchronous call to parser
parser.compileAsync (grammarString, 
    function (rules) {
        if (rules.errors.length > 0) {
            alert ("Grammar error count: " + tree.errors.length);
        } else {
            parser.parseAsync (rules.compiled, text,
                function (tree) {
                    if (tree.errors.length > 0) {
                        alert ("Text error count: " + tree.errors.length);
                    } else {
                    // to do something with tree.parsed
                    }
                },
                function (progress) {
                    progresPercent = Math.round(progress * 100) + "%";
                    return true;
                }
            )
        }
    },
    function (progress) {
        progressPercent = Math.round (progress * 100) + "%";
        return true;
    }
);

- grammar: string where a grammar is stored in textual format,
- done function: this function is called when parsing grammar is done. It takes
  compiled grammar or errors as parameter
- progress function:  this function is repeatedly called while parsing executes.
  If it returns false, parsing breaks

- rules: top rule
- text: text to parse by rules
- done function: this function is called when parsing text is done. It takes
  syntax tree or errors as a parameter
- progress function:  this function is repeatedly called while parsing executes.
  If it returns false, parsing breaks

- if a node is a token:
    - "value" property holds a string as a fragment of parsed text
- if a node is a choice:
    - "value" property holds a parsed sub-tree
- if a node is a tuple:
    - "value" property contains an array of tuple attributes’ sub-trees
- in all cases
    - "parsedBy" property holds a rule by which a node is parsed, where:
        - "name" property holds a name of the rule
        - "type" property holds one of strings: "token", "tuple" or "choice"
    - properties "from" and "to" hold integer positions of parsed node inside
      parsed string

function pTree (tree) {
    var tmp;
    if (tree.parsedBy.type === "choice") {
        alert (tree.parsedBy.name)
        pTree (tree.value);
    } else if (tree.parsedBy.type === "tuple") {
        alert (tree.parsedBy.name)
        for (var i = 0; i < tree.value.length; i++) {
            pTree (tree.value[i]);
        }
    } else if (tree.parsedBy.type === "token") {
        alert (tree.value);
    }
}
pTree (tree.parsed);

9. Errors

tree.errors[x] = {  
    absolutePosition: ...int...,
    line: ...int...,
    column: ...int...,
    description: ...string...
}

10. Conclusion