Manual Języka Programowania Lovage

# This grammar is designed for a predictive recursive-descent implementation.
# and intended to be LL(k) at the token level.
#
# In other words, whenever the parser is required to make a choice it must be
# able to choose "correctly" with constant token lookahead. This means that the
# handwritten recursive descent parser for this grammar can be implemented with
# worst-case linear run time rather than worst-case exponential runtime.
#
# All top-level syntactic decisions are bounded by token lookahead or by
# parsing a uniquely identified common prefix and then inspecting a bounded
# number of following tokens.
#
# The implementation does not perform general PEG backtracking.
# In particular, alternatives sharing a prefix are manually factored into
# the corresponding parse_* routine.
#
# See this paper for analysis of how LL(k) grammars relate to PEGs:
# https://arxiv.org/abs/1304.3177

Root <- ContainerMembers skip eof

Container <- LBRACE ContainerMembers RBRACE

ContainerMembers <- domain_doc_comment* (doc_comment* (Declaration / Descriptor / Expr))*

# *** Expressions ***

# The ;3 comments are parsed as expressions for diagnostics, but their resulting 
# nodes are discarded. Multiple expression comments may therefore occur consecutively 
# before the actual expression, being consumed before the actual expression. 

Expr <- (EXPRESSIONCOMMENT+ ExprBody)* ExprBody

ExprBody <- ExprNud ExprSuffix*

ExprSuffix <- (DOT2 / DOT3) ExprNud

ExprNud
    <- SimpleLiteral
     / MULTILINESTRINGLITERAL
     / BindingBody
     / Container
     / IndexSpace
     / PtrType
     / Signal
     / Operator
     / Polyadic
     / Assembly
     / Quote
     / Macro

ExprType <- (EXPRESSIONCOMMENT+ ExprTypeBody)* ExprTypeBody

ExprTypeBody <- (MonadicType / SignalType / ![Operator / Signal] ExprNud)

SimpleLiteral
    <- IDENTIFIER
     / BUILTIN
     / ORDINAL
     / NUMBERLITERAL
     / CHARLITERAL
     / STRINGLITERAL

# *** Signals ***

Signal <- KEYWORD_sig ((SignalMembers SignalBody) / SignalDoma / SignalLiftOp)

SignalType <- KEYWORD_sig SignalMembers ExprType

SignalDoma <- BACKSLASH KEYWORD_doma Container

SignalBody
    <- ExprType (DOT Expr)?
     / DOT Expr

SignalMembers <- LBRACE (Descriptor / Expr)* RBRACE 

SignalLiftOp <- BACKSLASH (PolyadicExtraOps / Polyadic / Operator)

# *** Pointers / Slices / Arrays ***

PtrType <- BACKSLASH Access? ExprType

IndexSpace <- LBRACKET (SlicePtrType / ArrayType / ArrayAccess)

SlicePtrType <- BACKSLASH? (COLON Expr)? RBRACKET Access? ExprType

ArrayType <- &(Expr) (COLON Expr)? RBRACKET ExprType

ArrayAccess <- (Access / Expr) Expr+ RBRACKET

# *** Invocations ***

MonadicType <- OP ExprType

# Is monadic unless continued by either dot (one more) or colon (two more).
Operator <- unclutter_operators OP Expr (DyadicTail / TriadicTail)?

DyadicTail <- DOT Expr

TriadicTail <- COLON Expr Expr

Polyadic <- LPAREN PolyadicMembers RPAREN

PolyadicExtraOps <- SimpleLiteral / COLON / DOT / DOT2 / DOT3 / Access # load/store/rmw

PolyadicMembers <- (OP / PolyadicExtraOps / ExprNud) (DescriptorStore / Expr)*

# *** Descriptors / Declarations ***

Access <- KEYWORD_rw / KEYWORD_ro / KEYWORD_wo

BindingDoma <- KEYWORD_doma ![Access]
BindingOut  <- KEYWORD_out ![KEYWORD_in]
BindingIn   <- KEYWORD_in ![KEYWORD_out]

BindingInOut
    <- KEYWORD_inout
     / (KEYWORD_in KEYWORD_out)
     / (KEYWORD_out KEYWORD_in)

Binding
    <- BindingDoma
     / BindingInOut
     / BindingOut
     / BindingIn

BindingBody <- Binding ExprType

# The descriptors participate in a domain's storage, region topology and compile-time seeds.
Descriptor <- (EXPRESSIONCOMMENT+ DescriptorBody)* DescriptorBody

# Store variant is standalone as polyadic shouldn't care about the storage variant as member. 
DescriptorBody 
    <- &(Binding* IDENTIFIER) COLON ExprType (DOT Expr)?
     / DescriptorStoreBody

DescriptorStore <- (EXPRESSIONCOMMENT+ DescriptorStoreBody)* DescriptorStoreBody

DescriptorStoreBody <- &(Binding* (IDENTIFIER / ORDINAL)) DOT Expr

# The declaration is a variable living in a region's namespace, and potentially instanced storage.
Declaration <- (EXPRESSIONCOMMENT+ DeclarationBody)* DeclarationBody

DeclarationBody <- DeclarationHeader IDENTIFIER (COLON ExprType)? DOT Expr

DeclarationHeader
    <- KEYWORD_doma Access
     / Access KEYWORD_doma?

# *** Macros ***

Quote <- BACKTICK+ QuoteTokenTree

# The `!eof .` rule must consume any non-EOF lexical token.
QuoteTokenTree
    <- QuoteUnquote
     / QuoteGroup
     / !(RPAREN / RBRACE / RBRACKET) !eof .

QuoteGroup
    <- LPAREN QuoteTokenTree* RPAREN
     / LBRACE QuoteTokenTree* RBRACE
     / LBRACKET QuoteTokenTree* RBRACKET

# Only meaningful while scanning inside a Quote;
QuoteUnquote <- COMMA IDENTIFIER

Macro <- KEYWORD_macro MacroBody

MacroBody 
    <- LBRACE domain_doc_comment* (doc_comment* MacroRules)* RBRACE
     / BACKSLASH MacroRules

MacroRules <- (EXPRESSIONCOMMENT+ MacroRulesBody)* MacroRulesBody

MacroRulesBody <- LBRACE MacroRulesDescriptor* RBRACE DOT ![Macro] Expr

MacroRulesDescriptor <- IDENTIFIER COLON BUILTIN DOT3?

# *** Inline assembly ***

# The optional identifier lists an explicit backend to consume this assembly.
Assembly <- KEYWORD_asm IDENTIFIER? LBRACE AssemblyMembers RBRACE

AssemblyMembers <- domain_doc_comment* (doc_comment* AssemblyStmt)*

AssemblyStmt <- (EXPRESSIONCOMMENT+ AssemblyStmtBody)* AssemblyStmtBody

AssemblyStmtBody
    <- AssemblyLabel
     / DOT? AssemblyInst
     / AssemblyDescriptor

AssemblyLabel <- &(IDENTIFIER) COLON AssemblyEndStmt

# Here the binding is required for storage, and store descriptors expect an assembly instruction.
AssemblyDescriptor
    <- Binding IDENTIFIER COLON ExprType (DOT Expr)? AssemblyEndStmt
     / (ORDINAL / BUILTIN) DOT AssemblyInst

AssemblyInst 
    <- IDENTIFIER (![skip_require_newline] Expr)*
     / LPAREN IDENTIFIER (DescriptorStore / Expr)* RPAREN

AssemblyEndStmt <- skip_require_newline / &(RBRACE)

# *** Tokens ***

# The source is decoded in its entirety from its external encoding into a
# stream of Unicode scalar values before lexical analysis begins.
#
# The supported source encodings are:
#   UTF-8       utf8_bom    <- '\357\273\277'       EF BB BF
#   UTF-16BE    utf16be_bom <- '\376\377'           FE FF
#   UTF-16LE    utf16le_bom <- '\377\376'           FF FE
#   UTF-32BE    utf32be_bom <- '\000\000\376\377'   00 00 FE FF
#   UTF-32LE    utf32le_bom <- '\377\376\000\000'   FF FE 00 00
#
# A source without a BOM is interpreted as UTF-8.
# https://en.wikipedia.org/wiki/Byte_order_mark
#
# Malformed source encoding is diagnosed by the normalization pass and never
# reaches the lexer or parser. On successful normalization, every element of
# the lexical input is one valid Unicode scalar value.
#
# Consequently, the lexical grammar below is completely independent of the
# source encoding and operates on Unicode scalar values rather than encoded
# bytes or code units.

# Unfortunately, there is not a standard way to match the start of the file in PEG.
# This rule definition is compatible with the original peg(1) tool but is not
# portable. It is however trivial to implement an equivalent rule in hand written
# parsers and other PEG tooling should have similar mechanisms.
#
# The normalization pass has already consumed the BOM.
sof <- &{ (yy->__pos == 0) } 
eof <- !.

# Unicode XID properties are checked by semantic predicates.
# These operate directly on the current Unicode scalar value
# supplied by the normalized source stream.
#
# unicode_xid_start <- &{ unicode_xid_start(yy) } non_control_char
# unicode_xid_continue <- &{ unicode_xid_continue(yy) } non_control_char
unicode_scalar <- [\200-(\000\016\255\255)]

unicode_xid_start <- [A-Za-z] / unicode_scalar
unicode_xid_continue <- [A-Za-z0-9] / unicode_scalar

# Exclude \177 which is DEL, but allow all other Unicode scalar values >= 0x80.
# In the normalized representation there is no distinction between ony-byte
# and multibyte source encodings anymore.
non_control_char <- [\040-\176] / unicode_scalar

digit <- [_0-9A-DF-OQ-Za-df-oq-z]
digit_int <- digit / [eEpP]
digit_float <- digit / [eEpP] [-+]?

NUMBERLITERAL
    <- skip [0-9] digit_int* &('.') digit_float+
     / skip [0-9] digit_float*

char_char
    <- '\\' non_control_char
     / !['\\] non_control_char
CHARLITERAL <- skip ['] char_char* [']

string_char
    <- '\\' non_control_char
     / !["\\] non_control_char
string <- ["] string_char* ["]
STRINGLITERAL <- skip string

line_string <- '\\\\' non_control_char* newline
MULTILINESTRINGLITERAL <- (skip line_string)+

line_comment
    <- ';' ![@;3] non_control_char* newline
     / ';;;' non_control_char* newline

# We forbid same-line doc comments to disambiguate the mapping to e.g. struct
# fields for documentation generation tooling.
doc_comment <- (sof / skip_require_newline) (skip ';;' non_control_char* newline)+
domain_doc_comment <- (skip ';@' non_control_char* newline)+

# This uses a positive lookahead rather than consuming input to make e.g.
# the newline terminating a multiline string literal or doc comment visible
# to the pre_op_white non-terminal.
newline <- &("\n" / "\r\n" / eof)
skip <- sof? ([ \n\t\r] / line_comment)*
skip_require_newline <- [ \t\r]* ([\n] / line_comment) skip

# An identifier may begin with a letter, underscore character or unicode_xid_start.
ident_begin <- '_' / unicode_xid_start

# We allow unicode and some ASCII characters as continuation in identifiers.
# These characters must not be tailing in a word, and apostrophe must be tailing instead.
ident_continue <- (op_char (unicode_xid_continue / skip)) / unicode_xid_continue

IDENTIFIER
    <- skip !keyword ident_begin ident_continue*
     / skip '@' string
BUILTIN <- skip '@' ident_begin ident_continue*

# Positional ordinal index to access anonymous bindings,
# also used with inline assembly SSA values.
ORDINAL <- skip '@' [0-9] digit_int*

# Operator tokens.
op_char <- [<>/|!?&#$%^~*=+\-]
OP <- skip op_char [.:]?

# Some whitespace rules to catch apparent "infix" expressions.
unclutter_operators
    <- ([ \n\t\r] / line_comment)+
     / &(RPAREN / LBRACE / RBRACE / LBRACKET / RBRACKET) 
     / &(OP / DOT / DOT2 / DOT3 / COLON / COMMA / BACKTICK / BACKSLASH)

EXPRESSIONCOMMENT           <- skip ';3'
BACKSLASH                   <- skip '\\'
BACKTICK                    <- skip '`'
COMMA                       <- skip ','
COLON                       <- skip ':'
DOT                         <- skip '.'     ![.]
DOT2                        <- skip '..'    ![.]
DOT3                        <- skip '...'
LPAREN                      <- skip '('
RPAREN                      <- skip ')'
LBRACE                      <- skip '{'
RBRACE                      <- skip '}'
LBRACKET                    <- skip '['
RBRACKET                    <- skip ']'

end_of_word <- !ident_continue
KEYWORD_asm     <- skip 'asm' end_of_word
KEYWORD_doma    <- skip 'doma' end_of_word
KEYWORD_in      <- skip 'in' end_of_word
KEYWORD_inout   <- skip 'inout' end_of_word
KEYWORD_out     <- skip 'out' end_of_word
KEYWORD_macro   <- skip 'macro' end_of_word
KEYWORD_ro      <- skip 'ro' end_of_word
KEYWORD_rw      <- skip 'rw' end_of_word
KEYWORD_sig     <- skip 'sig' end_of_word
KEYWORD_wo      <- skip 'wo' end_of_word

keyword
    <- KEYWORD_asm 
     / KEYWORD_doma
     / KEYWORD_in 
     / KEYWORD_inout 
     / KEYWORD_out 
     / KEYWORD_macro
     / KEYWORD_ro 
     / KEYWORD_rw 
     / KEYWORD_sig 
     / KEYWORD_wo