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]:
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
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
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."
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
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.