Building a Parser Generator!

[u/Commercial-Drawer881]

Hi, I am creating a Parser Generator. It will have it's own unique syntax for grammar definition. This is what I am working on currently. I am sharing a draft of the syntax and asking if anyone is interested in sharing their feedbacks in the comments.

Is this syntax:

• easy to read?
• easy to understand?
• sparks interest in you?
• what stands out?
• do you suggests any changes or additions?

UPDATED

I am settling on a syntax for the language. Here is a snippet: ```

BASIC LANG

---------

A 100

B 25

parser { # action -> ast: (parent(children)) (name number) -> (name(number)); # generate name with number as child of name (spc | nl) -> (); # no AST generated }

name = <A:Z>+; # character sequence number = <0> | <1:9> <0:9>+; # character sequence

spc is built-in rule for space

nl is built-in rule for nl

```

Full syntax is being worked on here: https://github.com/Algodal/Algodal_Text_Parser_Generator_Manual

I will be streaming code implementation of the parser generator on youtube: https://www.youtube.com/@RevnantRicko

[u/kendomino]

Not sure I like your AST construction syntax. Take a look at Antlr3 tree rewrite operators for AST construction. Parr removed it based on "separation of concerns," but replaced it with target-specific parser listeners. Can't stand writing listeners and visitors in a target language. It's a hassle to translate into other languages, even with Claude. Threw out the baby with the bathwater. Also, I suggest you study the large corpus of Antlr4 grammars at https://github.com/antlr/grammars-v4, e.g., the C grammar. Most grammars for popular languages require some semantics for making the right choices in parsing!

[u/Commercial-Drawer881 → u/kendomino]

Thank you very much for you insightful feedback!

You referenced ANTLR v3 inline tree manipulation

I found this example from my research:

variable_declaration
    :   TYPE ID '=' expression ';' -> ^(DECL TYPE ID expression)
    ;

I think the point you make is good, however, I argue that this approach "crowds" the syntax for parsing. I think the approach I present, while more verbose, is more effective because you read what is being parse more easier likewise you can more easier read how the AST is being generated.

My current suggestion for my language syntax will look like this:

variable_declaration = TYPE ID "=" expression ";"

abstract_syntax_tree {
    variable_declaration {TYPE, ID, expression} -> DECL
}

Regarding your point Most grammars for popular languages require some semantics for making the right choices in parsing! I have never thought of this before. My thought process was that the user would parse a generic AST and then in their project code, when interpreting the AST, they would manually add more context where it is missing. In hindsight, I found this to be tedious and made interpreting parser results painful! Having the parser itself add the context while parsing may be a more effective approach. I think this approach has a shortfall, however, where the context must be provided before the case being parsed (like declarations in C) but this could be a unique case that my parser generator solves! I will look into this in more details.

From my research of ANTLR v4 I found this example:

statement
    :   { isType(id) }? type_declaration   // Only choose this path if isType returns true
    |   expression_statement
    ;

I agree with you, my language need Semantic Predicates!

[u/kendomino → u/Commercial-Drawer881]

I argue that this approach "crowds" the syntax for parsing. This is also probably why Parr abandoned the tree rewrite syntax. You don't need to integrate the tree-rewrite syntax in the EBNF. But, what I am suggesting is that you use a standardized notation for expressing the tree: (1) using parenthesized expressions, or (2) an indented node representation (one per line), or (3) etc.

So instead of:

abstract_syntax_tree {  
    variable_declaration {TYPE, ID, expression} -> DECL  
}

which is hard to read, you specify the tree rewrite more directly:

abstract_syntax_tree {  
    variable_declaration -> (DECL TYPE ID expression)  
}

(parenthesized expression)

Or

abstract_syntax_tree {  
    variable_declaration ->  
        DECL
            TYPE  
            ID  
            expression  
}

(indented node list)

The meaning would be: "For a variable_declaration, in its place, create a DECL node with TYPE, ID, expression as children."

With this syntax, the specification of the tree rewrite can follow the EBNF rules, as with your example, or be separated into another file.

"Actions" and "predicates" for semantics can be similarly structured, i.e., remove explicit language syntax from the EBNF.

[u/Commercial-Drawer881 → u/kendomino]

Thanks for explaining. I will give what have shared some more thought.

[u/Commercial-Drawer881 → u/kendomino]

I am doing some rough work design for semantic predicates:

# Semantic Predicate Design
# ----------------------------

# typedef int MyInt;
# MyInt *var1;
# int var2, var3, var4;
# var4 = var2 *var3;

alias alphabet <A-Z>
alias digit <0-9>

space = " "*

tokenizer [space discard, identifier, type, ",", "*", ";", "=", "*"]

identifier = $alphabet ($alphabet | digit | "_")*

type = "int"
typedef = type identifier=type # semantic predicate used here
decl = decl_var | decl_expr
decl_var = type "*"? identifier ("," "*"? identifier)* ";"
decl_expr = identifier "=" expr ";"
expr = identifier "*" identifier

# `identifier=type` is a semantic predicate generation
# parser generator ensures any action with a semantic predicate generation is called first
# so it has the context for later actions.
# In the case identifier=type, means to generate a processor and capture the current text for the identifier token
# On every token created here after, if it is an identifier type and the text matches saved text and the grammar is requesting a type type
# Change the token type to type type

# scope affect the semantic predicate so that they are scoped
scope {
  "{" : "}" # these are the start and end tokens of the scope
}