This sections gives some explanations on how to write a language specification for Styx. Contrary to yacc, Styx is reflectively implemented, meaning it is written with it's own help. Thus, a proper Styx definition for the Styx language exists within the Styx source distribution. For omitted details you might like to refer to this source (styx.sty), from which we cite often in this part of the document. This does not only provides a proper definition, but also gives a plethora of examples.
Referring back to the above walk-through, a specification of a language is written down within one file consisting of three sections:
Language section stating the name of the language.Regular Grammar section defining the tokens.Context Free Grammar section, which, tautologically,
is the section where the context free grammar is defined.
start Source
:root : "Language" OptNat Ide
QlxDfns0
OptCfg
let OptCfg
:non :
:cfg : "Context" "Free" "Grammar"
Dfns
Conflicts
let QlxDfns0
:nil :
:ign0 : "Regular" "Grammar"
QlxDfns
An extra twist is implemented within the Styx generators.
As naming convention it is required that the Styx source files are named
like the corresponding languages and have the extension ".sty". Thus, if you
specify a language named "calc", you have to name the language definition
file "calc.sty".
The character set for the source is ASCII. For later reference, we distinguish between printable characters and control characters:
; Character Set
let Byte = '\00' .. '\ff' ; all extended ASCII
let Control = '\00' .. '\1f' ; control
| '\7f' ; DEL
| '\ff' ; space-like extended ASCII
let Printable = Byte - Control
Space, Newline, Return and Formfeed are used to separate tokens and are otherwise completely ignored. The source itself is format-free. Note that also the page separator character may be used, we do never refer the source by pages. Additionally, no tabulator characters may be used with in source. We had so many problems with different programs having different ideas about how to expand them, that we drooped them from this specification.
ign Space = " " ; ASCII - Space ign Line = "\n" | "\r\n" | "r" ; UNIX / DOS / Mac ign Page = "\p" ; weak separation convention
Comments start with a semicolon and extend to the end of the line.
; Comments et al
com Comment = ';' {Printable}
The regular tokens are Identifier (consisting of letters and digits, starting with a letter), three sorts of literals and a set operators.
; complex tokens
tok Ide = Letter {Letter} {Digit} ; Identifier
tok Nat = Digit+ ; Natural
tok Set = '\'' {LitChar} '\'' ; CharacterSet
tok Seq = '\"' {LitChar} '\"' ; CharacterSequence (String)
tok Opr = (Special - ';=<>')+ | '=<>' ; Operator
Beside the natural numbers, which are later used to denote characters by their ASCII code, we distinguish two sorts of strings form the literals. Single quoted strings denote sets of characters and double quoted strings sequences of characters. When containing only a single character, their meaning is of course identical.
Contrary to C syntax, both the single and the double quote has to be escaped when used inside these literals themselves. Additionally, a hexadecimal notation for (unicode) characters is provided within the character literals. Some control characters (form feed, return, newline, tabulator) can also be denoted within the quotation by a single character after the backslash.
For completeness, here are the remaining definitions for the literals:
; Definitions
let Letter = 'A'..'Z' | 'a'..'z'
let HexDigit = '0'..'9' | 'a'..'f'
let Digit = '0'..'9'
let Normal = Letter | Digit | Space
let Quote = '\'\"\`\\'
tok Parenthesis = '()[]{}' ; one character tokens
let Special = Printable - Normal - Parenthesis - Quote
let LitChar = Printable - Quote
| '\\' (Quote | 'prnt' | HexDigit HexDigit)
| '\\' 'xX' HexDigit HexDigit HexDigit HexDigit HexDigit HexDigit HexDigit HexDigit
The remaining tokens are operators and parenthesis. Both token classes do not have a meaning for themselves, but are used to form reserved words later in the regular grammar. Operators are made up from special characters.
The tokens in this section have a special meaning for the Styx preprocessor. They were introduced to provide modularization, macro expansion and conditional compilation.
; Preprocessing tokens
let White = Space | Line | Page
let Name = (Letter | "_") { Letter | Digit | "_" }
let MPar = ( Printable - ( White | ',' | ')' | '=' ) )
{ Printable - ( White | ',' | ')' | '=' ) }
tok MacInc = "#include" White {White} (Printable-White) {Printable-White} ; Include
tok MacDfn = "#macro" White {White} Name ; Macro definition
{White} [ "(" {White} MPar
{ {White} "," {White} MPar } {White} ")" {White} ]
[ "="
({Byte} - ({Byte} ("#macro"|"#end") {Byte}))
"#end" ]
tok MacSep = '\'' (Byte-'\'') [ '-' ] ; End of parameter
tok MacCond = ( ( "#ifdef" | "#ifndef" ) White {White} Name ) ; Conditionals
| "#else" | "#end"
The reserved words are "Language", "Regular", "Grammar", "Context", "Free", "let", "tok", "ign", "com", "ica", "ind", "lan", "InGroup", "ExGroup", "Group", "other", "start", "err" and "reduce". Further, "cons", "nil" and words starting with "ign" have a special meaning when used as production names. Since version 1.8 the production names "none" and "some" also have a special meaning in all grammar definitions with a version number (>=1).
Next to the introducing "Regular Grammar" keywords, the regular grammar is specified as a collection of equations. Following a leading keyword, that gives some hints how to cope with the equation, and eventually some option and group information (see below) a name is assigned to a regular expression. Have a look at the preceding definitions to get an idea who this looks like.
As with modern (f)lex implementations Styx now i.e. since version 1.6 supports the definition of inclusive or exclusive groups of regular expressions, too. They are useful to switch between different regular languages. ( see Example05 for a demonstration )
Version 2.0.1 introduces "dynamic" tokens. They are declared to the parser with the QlxDfn-production "defd" and initially unknown to the scanner, i.e. have no regular expressions. With the help of a special member production token values are assigned to them during the parse process. ( see Example08 for a demonstration )
; REG-Section
let QlxDfns ; Qlx-Definitions
:nil :
:cons : QlxDfn
QlxDfns
let QlxDfn ; Qlx-Definition
:defn : QlxCat QlxOpt QlxGrp0 Ide QlxGrp1 "=" ExpQuot ; regular expression definition
:defd : "tok" "<" Ide ">" ; dynamic token
:igrp : "InGroup" Ide ; inclusive group definition
:xgrp : "ExGroup" Ide ; exclusive group definition
!tgrp : "ExGroup" Ide "[" "tok" "]" ; and ignore keywords in group (version >= 2.0.1)
:mgrp : "Group" Ide = Ids ; group list definition, introduced in version 1.7
let Ids ; Group list members
:cons: Ide Ids0 ; 'Ide' can refer to a QlxGroup or the language as initial QlxGroup.
let Ids0
:nil :
:cons: Ide Ids0
let QlxGrp
:non : ; no group information
let QlxGrp0
:grp : ":" Ide ":" ; The regular expression belongs to QlxGroup or group list 'Ide'.
:ign0 : QlxGrp ; The regular expression belong to initial QlxGroup.
let QlxGrp1
:grp : "!" Ide ; The recognition of the regular expression activates QlxGroup 'Ide'.
:igrp : "!" ; The recognition of the regular expression activates initial QlxGroup.
; The following definitions has been added in version 1.7:
:pgrp : "!+" Ide ; The recognition of the regular expression pushes the current QlxGroup onto the stack
; and activates QlxGroup 'Ide'.
:pigrp: "!+" ; The recognition of the regular expression pushes the current QlxGroup onto the stack
; and activates initial QlxGroup.
:pop : "!-" ; The recognition of the regular expression pops and activates the top QlxGroup on the stack.
:ign0 : QlxGrp
let QlxCat ; QlxCategory
:letC : "let"
:tokC : "tok"
:indC : "ind"
:lanC : "lan" ; Embedded language:
; lan :Ide_Language: Ide_Startsymbol ! Ide_EofOrFollowTokenLanguage = Ide_EofOrFollowToken+
:ignC : "ign"
:comC : "com"
Groups and group lists must be defined before they can be referenced. With this exception the definitions can come in any order. This means that an applied occurrence does not need to follow it's definition textually. It is only required that no recursion is used. So, you can order the definitions due to other purposes. Note that contrary to the lex program no implicit semantics is placed on the order of the definitions, too.
The leading keyword in the equations (see QlxCat) describes the usage of a token. First, the equations introduced using "let" are auxiliary. They do not specify tokens but only regular sets eventually used in them. As a consequence they can't neither be grouped nor switch to some group. See in the above section for typical applications of this feature.
The next keyword "tok" introduces regular tokens. The identifier following this keyword and the optional option and group information are the only ones that can later be used within the context free grammar. Also, when implicitly used there as keywords, only these regular sets will be considered.
In order to support the specification of indented languages (since version 1.6), the keyword "ind" introduces so-called indent tokens as regular tokens. In the context free grammar they will be referenced by the corresponding minimal indent and dedent keywords. ( see Example06 for a demonstration )
Another regular token variant (since version 1.6) are the so-called embedded language tokens. They are introduced by the keyword "lan" and their values are not just strings but trees i.e. terms. Within such a definition the initial keyword must be followed by the name of the embedded language, the start symbol from which the parsing process should start and either the name of the "hosting" language along with a list of follow tokens or the name of the embedded language along with a list of so-called eof tokens.
In the context free grammar they are referenced by concatenating the names of the embedded language and the start symbol. ( look at the XML language definition in the reference section for a demonstration )
Last, the remaining keywords ("ign" and "com") introduce tokens that will be more or less ignored. "com" is for comments, and the semantic is, that they will be stored in the derivation tree (for evtl. source-source translation), but will not be accessible through the language specific interface. Also, both "com" and "ign" tokens can be inserted at any place within the language sources.
"ign" tokens are completely ignored and never even leave the scanner. Conceptually, they do their duty as formatting character. Because the scanner knows about the newline character and provides line and column position with each token, these classes of characters may (somehow indirect) be accessible in the source tree later. If no strange things are done with the control characters (i.e. only uses space and newline as formatters), on can fully reproduce the source from the derivation tree modulo trailing spaces and empty lines.
Collectively, all definitions beside the "let" ones are considered to form the tokens of the language. Styx's lexical analyzer requires from each of these token definitions that they are disjunctive from each other. So, no two of them may contain the same word. While the lex program resolves possible non-empty intersection by an implicit "priority", one has to make this explicit when using Styx. There are many ways to do this. One possibility is to use the difference operator ("-") to clarify the situation. Styx will issue errors as soon as non-empty intersections are detected.
In the language interface, the tokens will be offered as symbols. Basically, these are unique strings allowing them to be compared by the C identity predicate ("=="). String equal tokens will only stored once by this mean, too.
This can become a disadvantage when the tokens are abnormally defined within the language. Although we considered this a weak design anyway, few means are provided to introduce a normalizer for such tokens. In order to support case insensitive languages, a normalizer for these is build into Styx.
let QlxOpt ; QlxOption :non : :ignca: "[" "ica" "]"The "[ica]" option before the defined identifier indicates that the case has to be ignored. As a result all of the corresponding token values will be normalized to small letters. Note that using abnormal tokens has many disadvantages, among others a possible lost of source information. People who define such abnormalities are typically unable to decide whether they really mean what they do. I've seen, for example, PASCAL implementations, which were case insensitive but identifiers like "FileRead" being defined in them. This certainly means asking for trouble. We cannot help bad design and strongly suggest not to use normalizers on tokens.
Here we finally come to the right hand side of the regular equations.
let Exp4 ; Expression prio 4 :sequ : Seq :set : Set :ident: Ide
The meaning of the set and sequence literals has already been defined when these token were introduced. The identifier denotes the regular set corresponding to some other equation.
let Exp3 ; Expression prio 3
:ign1 : Exp4
:range: Exp4 ".." Exp4
:ign2 : "(" Exp ")"
Round parenthesis may be used to group expressions, the double dot operator ".." can be applied to construct character ranges. It's both arguments have to be single characters.
let Exp2 ; Expression prio 2
:opt : "[" Exp "]"
:star : "{" Exp "}"
:puls0: Exp "*"
:plus : Exp3 "+"
:plusn: Exp3 Limit
:ign1 : Exp3
let Limit ; occurrence limit
:ntime: Nat ; exact ntimes
:range: Nat "," OptNat ; minimum and optional maximum
let OptNat
:non :
:nat : Nat
Next in binding strength come the different sorts of monoids and options. The "+" suffix means one or more occurrences. The curly brackets or, since version 1.7, the "*" suffix is for zero or more occurrences and the square brackets means zero or one occurrence. Limited occurrences ( introduced in version 1.7 ) can be expressed by specifying a number or a range.
let Exp1 ; Expression prio 1 :conc : Exp1 Exp2 :ign1 : Exp2
The concatenation is denoted by simply concatenating expressions. The corresponding operator is omitted.
let Exp ; Expression prio 0 :union: Exp "|" Exp1 :diff : Exp "-" Exp1 :ign1 : Exp1
Finally, and weakest in binding strength, we have the set union ("|") and difference ("-") operations.
The following definitions refer to version 1.6, 1.7 and above. They introduce dyck, pattern and quotient expressions in order to cope with nested and heredoc comments, among others.
Quotient expressions are introduced in version 1.7. The quotient part of the expression can be a non-unicode character set or a sequence. ".." within the character set denotes a character range. In the first case, all characters belonging to the set will be stripped from the end of the token and re-scanned. In the second case, the defined sequence will be stripped from the end of the token and re-scanned. The scanner reports an error if the token doesn't end with that sequence.
let ExpQuot ; quotient :quot : ExpDyck "/" Exp4 ; Exp4 = Set or Seq :ign0 : ExpDyck
Dyck expressions, introduced in version 1.6, specify the left parenthesis, the inner part and the right parenthesis. To give an example, < /* > < */ > describe recursive C-like comments.
Pattern expressions are introduced in version 1.7. The production 'spat' specifies a start pattern token. The non-unicode character set argument constitutes the pattern, while the expression arguments constitutes the pattern prefix and suffix. ".." within the character set denotes a character range. There must always be a corresponding end pattern token of production 'epat' which tries to match the current start pattern. The ID of the end pattern token refers to the non-matching case.
let ExpDyck ; dyck ( Exp ) :dyck : "<" Exp ">" Exp0 "<" Exp ">" :spat : "<" "=" Exp0 ">" Set "<" Exp0 ">" :epat : "<" "?" Exp0 ">" Ide "<" Exp0 ">" ; Ide = start token ID :ign0 : Exp let Exp0 :non : ; no restriction on the inner part :ign0 : Exp
Here we deal with the definition of the context free grammar section in the Styx sources. This is straight forward and basically a triple list.
On the top level we have a list of definitions (Dfns) of non-terminal identifiers, whose body consist of a list of productions (Prds) for these non-terminals, again each identified by a name. The body of the individual productions is formed by a list of members (Mbrs), which are either identifiers denoting terminals or non-terminals, strings denoting keywords or a non-specified sequence denoted by the keyword "[other]".
Since version 1.8 Styx supports an EBNF-like notation for list ans optional members. (see the member syntax below and Example02 for an application)
With the help of the member production "dtok" it is possible to introduce an as token X parsed value V as dynamic token Y, where X, Y are denoted by the left and right token identifiers. From that position within the parse process the scanner always reports V as Y. (styx version >= 2.0.1)
The non-terminal names defined have to be unique within the scope of the source and disjunctive from the names of the regular sets defined in the previous section. The production names have to be unique within each non-terminal definition.
The keywords (string members) have to belong to one of the defined regular sets of tokens.
; CFG-Section
let Dfns ; Definitions
:nil :
:cons : Dfn
Dfns
let Dfn ; Definition
:defn : Cat DfnOpt Ide
Prds
let Prds ; Productions
:nil :
:cons : Prd
Prds
let Prd ; Production
:prod : Lay Ide ":"
Mbrs
let Mbrs ; Members
:nil :
:cons : Mbr
Mbrs
let Mbr ; Member
; keywords
:tkm : Seq
; fallback for a non-grammatical source sequence
:else : "[" "other" "]"
:ign0 : Mbr1
let Mbr1 ; Member
; (dynamic) token or nonterminal
:ntm : Ide
; EBNF extension: optional list member
:klst0: "[" OptKey Mbr1 OptKey "..." OptKey "]"
; EBNF extension: mandantory list member
:klst1: "(" OptKey Mbr1 OptKey "..." OptKey ")"
; EBNF extension: optional member
:opt : "[" OptKey Mbr1 OptKey "]"
; introduction of dynamic token
:dtok : Ide "<" Ide ">"
let OptKey
:nil :
:cons : Seq OptKey
Some options extend this construction, of which the most important is the distinction between start and inner productions. Start productions indicate those non-terminals which can later be parsed individually, while the inner productions can only be parsed as part of a start production. Referring back to the regular grammar specification this distinction is much like the "let" and "tok" categories. We use a similar syntactic construction for the distinction, a leading keyword. The start productions are indicated by a leading "start" and the inner productions by a leading "let".
let Cat ; Category :letC : "let" :bgnC : "start"
The remaining options deal with error recovery and pretty printing.
Use the error option to specify a non-terminal as resumption point within the implemented panic-mode error recovery. To enforce the default error handling where the parse process stops when a syntax error occurs you should omit the error option.
let DfnOpt ; DfnOption :non : :errnt: "[" "err" "]"
The layout option gives the pretty printer some hints for the layout of the corresponding grammar phrases. Choose the colon (":") as default or if you aren't interested in that facility. ( look at the layout specification for details )
let Lay :reg : ":" :line : "?" :nof : "!"
Often language definitions are ambigous w.r.t LALR(1) parsing. As stated above one example is the function call and expression syntax of Lua. (see the styx grammar lua.sty which is part of Example07 as an application)
let Conflicts ; Conflict rules
:nil :
:cons : Conflict
Conflicts
let Conflict ; Conflict rule (according diagnostic output)
:defn : "Context" State "." Token ":"
Rules
let State ; Conflict state
:nat : Nat ; state index
:seq : Seq ; state symbol (keyword)
:ide : Ide ; state symbol (token, nonterminal)
let Token ; Conflict token
:seq : Seq
:ide : Ide
let Rules0
:nil :
:cons : Rule
Rules0
let Rules ; Conflicting reduce productions, explicitly ordered
:cons : Rule
Rules0
let Rule
:red : "reduce" Ide "." Ide ; Conflicting reduce production
Some of the identifiers for the production names are reserved for normalization. These are "cons(0-9)*", "nil(0-9)*" and "ign(0-9)+". Beside other keywords used in the Styx grammar, you are otherwise free to chose these names. The mentioned identifiers serve it's duty as indications of how to make up the depth grammar. A separate section is devoted to this topic. See below.
As stated above since version 1.8 if hinted by a version number in the language section of the grammar definition the production names "none" and "some" are reserved for normalisation, too.