1
$\begingroup$

We're creating our own programming language for a subject. And we're confused whether to add the names of the functions we want to have in our language (like our own version of print) in the BNF grammar.

Reserved words should be recognized by the lexer, right? How about function names?

$\endgroup$
  • $\begingroup$ I don't conceptual issues with either decision. This may be a matter of taste, rendering the question subjective. Community votes, please: close as primarily opinion-based? $\endgroup$ – Raphael May 27 '16 at 11:20
  • $\begingroup$ Think very hard about whether you truly want to have two separate mechanisms for identifying function calls/identifiers. $\endgroup$ – Raphael May 27 '16 at 11:23
  • $\begingroup$ Are your function names actually reserved or not? Often the difference between keywords and built-in function names is that the latter may be used as regular identifiers, shadowing the original built-in function. In that case, I would find it inadvisable to hardwire them in the grammar. $\endgroup$ – Emil Jeřábek May 27 '16 at 16:42
5
$\begingroup$

If your language has a small set of functions and there is no mechanism for adding other ones, then you could include the function names as keywords. But that's not a very likely scenario, unless your "language" is just a desk calculator (and even then, these days many calculators allow you to define functions).

So in general, it's not going to be feasible to include all the function names in the lexer, and unless function names are somehow lexically distinguished from other identifiers, all the lexer can do is report that it has found an identifier.

Assuming the grammar is unambiguous, a common idiom is to use a unit rule in the BNF in order to encapsulate whatever needs to be done to turn an identifier into a function reference (and similarly for identifiers representing other kinds of things) [Note 1][Note 2]:

function_name: IDENTIFIER
type_name:     IDENTIFIER
...

term:          function_name '(' optional_expresion_list ')'

But that won't work if certain expressions in the language would be ambiguous without knowing whether an identifier in the expression names a function or some other kind of thing. That's not very common for function names, but C and derived languages famously feature an analogous ambiguity with type names in C.

It's not totally unknown, though. For example, in awk, string concatenation is expressed with simple operand juxtaposition, so that

first "-" second

is the concatenation of two variables and a string containing a dash. The result is that

first (second)

is ambiguous: if first names a function, it could only be a function call; otherwise, it could only be string concatenation. If the language insists of declaration before use (awk doesn't), it would be possible to disambiguate by distinguishing according to the type of first.

The implementation involves sharing a symbol table between the parser and the scanner. The scanner looks each identifier up in the symbol table, and returns a token based on the broad type (or "kind") of symbol. If the scanner does not find the symbol, it will return a token of type UNDEFINED_SYMBOL or some such, which will be required (or at least allowed) in grammar rules where a new symbol is defined.

This technique is commonly called "semantic feedback". Much care must be taken to ensure that the symbol table seen by the lexer while it is examining a token corresponds to the actual semantic state at the moment in which the parser is examining the token. Since lexers typically consume tokens in advance of the parse (or at least one token), this guarantee is not as easy as it might look at first glance.

Semantic feedback is often discouraged, both because of this fragility and because it contaminates the lexer with data which should be private to the parser. But sometimes it is the simplest solution.

As it happens, awk does not use this approach, in part because it does not require functions to be declared prior to use. Instead, it has a whitespace-aware lexical rule: a parenthesis which immediately follows an identifier without intervening whitespace is used in a function call expression; if there is intervening whitespace, the parenthesis must be a grouping parenthesis and the expression is treated as a concatenation. This rule is the source of occasional confusion about apparently mysterious errors (see below).

That rule could be expressed in two ways (at least):

  • The lexer could return a FUNCTION_NAME token when it sees that the character immediately following an identifier is a (. In that case, the grammar might include

    term: FUNCTION_NAME '(' optional_parameter_list ')'
        | '(' expression ')'
    
  • The lexer could distinguish between two kinds of open parenthesis: a parenthesis which immediately follows an identifier, and all the other ones. So then the grammar might include:

    term: function_name OPEN_APPLY optional_parameter_list ')'
        | '(' expression ')'
    

(A third possibility exists, in which the function name and the following parenthesis are recognized as a single token, leading to the rather odd-looking grammar rule FUNCTION_NAME optional_parameter_list ')'. Some real-world implementations actually use this for efficiency, but it's confusing for the reader.)

Editorial comment (i.e. my opinion)

On the whole, you should attempt to avoid playing tricks in your lexer. Ambiguities like the ones mentioned above should be treated as flaws in the language design rather than challenges to be overcome by clever hacks in the parser, particularly if you are designing a language. History demonstrates that ambiguities like the above not only complicate parsers, but also confuse people using the language in question.

A casual search for "most vexing parse" will show the extent of confusion created by an ambiguity in the C++ language. And the use of juxtaposition for concatenation in awk creates so many confusing parse errors that the Gnu awk manual has a chapter about how to write concatenation, citing the alleged explanation for the syntax given by one of the awk authors: "It seemed like a good idea at the time."

Notes

  1. In this post, I use yacc syntax for the BNF, with the convention that terminals (tokens) are represented either by UPPER_CASE or by quoted characters, and non-terminals are spelled in lower_case.

  2. While some languages might be content to not allow higher-order types, almost all languages -- even C -- allow the target of a function application expression to be a computed value. So if you find yourself writing the above rule, you might want to think about its implications for the semantics of your language.

$\endgroup$
0
$\begingroup$

Let me give an illiterate answer. They should not. Not at parser level, and not at scanner level, for sure. Scanner should generate identifier token. Since there is no functional difference between built-in and user-defined functions at parser level, you should not differentiate them. It is at semantic, compiler level that you make the difference by precluding the re-definitions. The difference is irrelevant at AST level. You parse only once, I suppose and re-evaluate the parsed AST later, when dependencies changes.

Despite I expose my opinion here, I wonder how easily you ascribe questions to the opinion-based class. This question is certainly answerable. You can easily collect all pros and cons. Every language designer needs the answer in practice. These answers must be a part of every parser book.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.