I just started looking through the CMake Language and associated BNF. It might be useful to see if your language is suitable for a LALR(1) parser generator (bison) or a LL(1) parser generator (ANTLR) after separating lexemes from BNF. A few comments which I’m confused over:
There is no description of the BNF meta language, for example, <match…>, ?, ‘*’ , ‘+’. I assume the following definitions
?: 0 or 1 instance.
*: 0 or more instances.
+: 1 or more instances.
<match ..> defines some lexical characteristics but is itself ambiguous, that is there are some inconsistencies in the definition.
The BNF describing spaces in statements seems difficult to understand. Either a simple statement that “where one space is allowed, many can be used” with either BNF or verbiage to support the allowable or required language elements where this applies to. The use of space* is confusing.
Legal CMakeList.txt files:
An empty file.
A file consisting of an indefinite number or either newlines and/or comments.
A file with a mixture of the above and expressions.
The following syntax appears ambiguous: arguments ::= argument? separated_arguments* separated_arguments ::= separation+ argument? | separation* '(' arguments ')'
The reason is that argument? and separated_arguments* appear to conflict for a single argument. The BNF reduction is ambiguous, it is not an LR(1) language.
Using BNF for a LALR grammer in its non-expanded form (w/o ‘*’, ‘?’, ‘+’) we get:
arguments := arguments space argument | argument |
argument := unquoted string | quoted string | Lua thing
There is a Lua example but no reason given for why it is needed. To my humble eyes a quoted string, “string …”, with or without newlines would serve the same purpose.
Separation of lexemes is not done. Identification of lexemes in BNF is firstly a mistake, and leads to things like <match …>, I assume match is meant to define lexemes.
is something like the below legal in your BNF? command( argument1 # comment argument2 # comment )
An excellent and pragmatic source for actual structure of language descriptions and the impact of separating lexemes from BNF is the book C: A Language Reference Manual by Harbison and Steele. I have found edition 2/3 to be quite good with following editions tending to academic representations. In this book you can see a clear separation of lexemes from BNF, and can look at its consequences.
The C: A Language Reference Manual, with suitable alterations, exactly matches what you are trying to achieve in your CMake Language description.
Thanks. The language was not originally designed with a formal grammar. The BNF is an attempt at formally documenting what the implementation does. I’d welcome merge requests clarifying the BNF documentation w.r.t. the implementation, or its presentation in general.
I will take a hand at clarifying the BNF but it will need review and oversight since I do not know CMake (I’m just trying to learn it).
Note that your document forces three types of BNF:
(1) BNF meant for CMake users.
(2) Formal BNF, meant for parser generators.
(3) Lexeme (token) BNF meant for lexers.
My inclination is to provide a separate description of the lexer and give the BNF for the formal grammar. The Harbison and Steele book, C: Language Reference Manual, provides an excellent example of both how to do that and what the reader’s consequences are. But, that will take several weeks and I don’t think I have the time.
Thanks. I’d prefer not to make major organizational changes. If there are subtle mistakes they can be fixed. Those wishing to understand the lexer can look at our source code.
It is tedious but not particularly difficult to create a formal grammar for the language. The conditions needed to do this are already in place. What is needed is a change in organization and creation of appropriate representations. Since the prerequisite conditions are in place, it is a ‘done deal’. So, the quick answer is that someone who knows CMake and knows compiler design and construction should be able to do it.
Since I don’t know CMake it would be a labor. I’d have to read through what is there, understand and reorganize it, and create the required formal grammar. Then, if I were diligent, I’d run the grammars through Bison or ANTLR, and correct the mistakes, And if I had any sense, I’d communicate with those more knowledgeable to change what exists to what should be there.
Now, if there is a general by-in by the chief scientist (?) and the developers I can take a hand at it. If not, then Oh Well.
In 1964 a general API was created to handle lists, and directed acyclic graphs (DAGs). This framework appears suitable for all of the work so far seen that CMake does with respect to dependency trees et alia.
As part of this effort I constructed I/O functions. The Input lexer contains much of the work that you have already done, plus some things not already done. In short, the I/O is developed to be self-testing (Output(Input) == Output), and the actual I/O functionality is abstracted. I am including the source code for the lexer. It contains both a description (in Doxygen) of the lexemes and an implementation. I assume that you do something similar, but the emphasis is on the description, a preamble to the language syntax equations.
Whoops. Sorry. “New users can not upload attachments”.
The grammar is documented in Help/manual/cmake-language.7.rst. As stated above I’m not interested in major reorganization of that document. It is not trying to be a normative specification.
If someone wants to write a formal grammar in a machine readable format we can include that with a link to download. We already do this for JSON schemas.
There is no ambiguity. argument? cannot match a single argument preceded by separation, and separated_arguments* cannot match arguments without leading separation or (.
It is an example of one of our three argument types: a bracket argument. The difference from a quoted argument is stated in its documentation: No evaluation of the enclosed content...is performed.
Thanks. I am reading Help/manual/cmake-language.7.rst. I took a glance at the parser and a look at the lexer. The lexer appears to be something geared to flex, the parser appears to be hand-built. Don't know for sure.
As to the lexer, it is slow and conventional. I was unable to upload the lexer I built for my version of Slip (gslip). It is hand-built, and not a flex or similar lexer. The hand-built nature provides for several speed improvements over the generated files from a lexer generator. I would estimate something like an order of magnitude improvement of speed, not sure, didn’t check. I didn’t look carefully at the code. I assume you used something like flex to generate the code.
The lexer code I glanced at seems overly complex. If I have time, I will look at it more closely to see what it does. I do note that it is undocumented which I find strange in this day and age. My lexers are simpler by comparison. They discard space, line feeds and comments. They return tokens representing, in your domain, arguments, strings, separators (which would be quoted in the BNF) and discrete tokens for commands, statements and etc. Your lexer seems to do more. The parser, in my work, is responsible for all the dirty work.
The LL(1) parser I haven’t looked at. Using an LL(1) parser gives an improvement in error handling, so that would be my first comment. But although it’s tedious, sometimes very tedious, it is possible to build your own. Can’t upload my file. Can’t show you an alternate viewpoint.
Back in 2014 I implemented the Input part of Slip (gslip) using bison and flex to good advantage. I changed this time to a hand crafted solution because of speed and a dislike in making my development dependent on a moving platform. But, that is a personal decision.
In a separate note, since you have an LL(1) parser I assume that you have a BNF driver for it. If so, then this could be a direct replacement for some of the BNF in the language document. At least at a high level.
is ambiguous. An input of’ ‘argument’ can be reduced to ‘arguments ::= argument’ or ‘separated_arguments ::= separation+ argument?’. Since ‘separation ::= space’ it appears that any ‘argument’ preceded by a space has two reductions. And since the first reduction, ‘arguments ::= argument?’ can have 0 or 1 instance we are able to assume that it is missing (0) and choose the ‘separated_arguments’ as a reduction or assume it’s present choosing ‘arguments’ as a reduction. It is ambiguous.
Am I incorrect in saying that a LUA argument can be replaced by a quoted argument? And if not, your comment on ‘evaluation’ comes to mind, there are more conventional representations of defining an evaluation element as an argument. In procedural languages such as C, C#, C++, Java, Pascal, evaluation of an argument is noted by a syntax such as identifier ‘’(’ arguments* ‘)’, where the identifier is some known executable function the parentheses required and the arguments optional.
At other points of the language there is an indication that something like identifier ‘(’ arguments ‘)’ is acceptable. I’m going to have to reread those areas so that I understand them better, but on the face of it you seem to have already allowed for some sort of standard mechanism for defining evaluate arguments.
No it can’t. Separation tokens are explicit, and separation+ matches “at least one separator”. An input stream consisting of only argument does not offer a leading separator to match in separated_arguments.
Sure, but at the cost of explicitly escaping all the things that might be evaluated. Bracket arguments allow embedding arbitrary content with minimal markup.
I concede the point. I can’t generate a counter example. Sigh. All is lost.
But now to BNF. Saying that where one space is allowed many can be used, and then
arguments ::= arguments space argument | argument
seems somewhat simpler.
And saying that
space ::= <match '[ \b \f \n \r \t]'> | comment
would seem to complete the syntax and allows for comments, as in
argument # comment\n argument …
Oh and I guess, you have to say that ‘#…’ triggers a single line comment, which means that a comment ends at a line end, either \r\n or \n.
Now as to the lexer, the lexer would return ‘argument’ but would never return space or a comment. The token received by the parser is relieved of any obligation in treating the input and can go about its business.
I don’t know CMake (which should be obvious to the most casual observer), but in programming I have found few needs to put escape sequences in strings, and given the ability to do so easily, I suspect I would still find few needs. But, since I don’t understand CMake, I’m not sure how relevant this is. In particular, the importance of this feature as an argument to some function. Why would you put an escaped character in as an argument? From what I’ve seen (Step 1), the input arguments to CMake functions do not seem to need this, and given the expanded set of commands, e.g., ‘if’, it would seem to be productively avoided.
If handles octal, decimal, and hexadecimal numbers
It handles single line comments (//) and multi-line comments (/* */)
Input has been abstracted allowing stdin, strings, or a user defined input type.
It uses a Mealy Finite State Machine (FSM)
It uses mapping tables rather than procedural code, faster and uses less memory.
It does not handle LUA things.
It does not return comments, newline, spaces, … .
The parser accepts the tokens and verifies that they are grammatically correct. Being hand crafted a Mealy FSM machine was used and a push-down automata was unnecessary.
In this context the accepted LALR(1) BNF for an argument would be:
I’ve had to count escapes a number of times. The problems usually arise when doing install(CODE) or other codegen of CMake (or CMake-adjacent) syntaxes where $ (or even ") show up naturally. Once you have a block of 5 lines where you have to think about the CMake escaping on top of whatever syntax you’re actually trying to write, bracket syntax becomes useful. Not too dissimilar to writing complicated shell scripts inside of YAML and having to think about the same kinds of layering issues. Once you’re past a few lines, it is usually best to just configure_file a larger block.