смежность как оператор - может ли с этим справиться любой лексер?

Невидимые операторы не могут быть распознаны с помощью лексического анализа по причинам, которые должны быть более или менее очевидными. Вы можете определить наличие невидимого оператора, только проанализировав синтаксический контекст, который является ролью синтаксического анализатора.

Конечно, большинство инструментов лексического анализа позволяют выполнять произвольный код для каждой распознанной лексемы, поэтому ничто не мешает вам встроить конечный автомат или даже полный синтаксический анализатор в лексический сканер. Это редко бывает хорошим дизайном.

Если ваш язык однозначен, то в вашей грамматике нет проблем с обработкой смежности. Но нужно соблюдать некоторую осторожность. Например, вы редко хотели бы, чтобы x-4 анализировалось как умножение x и -4, но наивная грамматика, которая включала, например,

expr -> term | expr '-' term
term -> factor | term factor | term '*' factor
factor -> ID | NUMBER | '(' expr ')' | '-' factor

будет включать эту двусмысленность. Чтобы решить эту проблему, вам нужно запретить производство смежности со вторым операндом, начинающимся с унарного оператора:

expr -> term | expr '-' term
term -> factor | term item | term '*' factor
factor -> item | '-' factor
item -> ID | NUMBER | '(' expr ')'

Обратите внимание на разницу между term -> term '*' factor, которая допускает x * - y, и term -> term base, которая не допускает x - y (expr -> expr '-' term распознает x - y как вычитание).

Примеры контекстно-свободных грамматик, допускающих смежность в качестве оператора, см., например, в Awk, в котором смежность представляет собой конкатенацию строк, и в Haskell, в котором она представляет собой применение функции.

Поскольку этот вопрос возникает время от времени, на SO уже есть ряд соответствующих ответов. Вот некоторые из них:

• Разбор последовательности выражений с использованием yacc. Невидимый оператор приложения функции. Использует yacc/bison; включает как явные, так и основанные на приоритетах решения

• yacc — приоритет правила без оператора? Невидимый оператор конкатенации строк. Использует Ply (генератор парсеров Python)

• Конкатенация сдвиг-уменьшение конфликта Еще один невидимый оператор конкатенации. Использует JavaCUP.

• Анализ последовательности выражений с помощью yacc Невидимый оператор приложения функции. Использует fsyacc (генератор синтаксического анализатора F#)

• Использование приоритета yacc для правил без терминалов, только без терминалов. Смежность в обычных математических выражениях. Использует yacc/bison с правилами приоритета.

• bison/yacc - ограничения настроек приоритета. Смежность приложений функций, подобных Haskell. Использует yacc/bison с правилами приоритета.

Вот один пример использования pyparsing в Python:

import pyparsing as pp

integer = pp.pyparsing_common.integer()
variable = pp.oneOf(list("abcdefghijklmnopqrstuvwxyz"))

base_operand = integer | variable

implied_multiplication = pp.Empty().addParseAction(lambda: "*")
expr = pp.infixNotation(base_operand,
                [
                    ("**", 2, pp.opAssoc.LEFT),
                    (implied_multiplication, 2, pp.opAssoc.LEFT),
                    (pp.oneOf("+ -"), 1, pp.opAssoc.RIGHT),
                    (pp.oneOf("* /"), 2, pp.opAssoc.LEFT),
                    (pp.oneOf("+ -"), 2, pp.opAssoc.LEFT),
                ])

Это предполагает, что переменные - это просто отдельные символы. Существует также некоторая подтасовка приоритета операций, чтобы заставить работать смежность, возведение в степень и опережающие знаки. Действие синтаксического анализа, добавленное к выражению implied_multiplication, должно показать вставку оператора умножения.

Вот некоторый тестовый вывод:

tests = """
    x-4
    ax**2 + bx +c
    ax**2-bx+c
    mx+b
    """
expr.runTests(tests, fullDump=False)

печатает:

x-4
[['x', '-', 4]]

ax**2 + bx +c
[[['a', '*', ['x', '**', 2]], '+', ['b', '*', 'x'], '+', 'c']]

ax**2-bx+c
[[['a', '*', ['x', '**', 2]], '-', ['b', '*', 'x'], '+', 'c']]

mx+b
[[['m', '*', 'x'], '+', 'b']]

Если токены не имеют фиксированной длины, вы должны разделять соседние токены одного типа каким-либо другим токеном или пробелом. Язык программирования Gosu включает смежность для реализации " выражения", поддерживающие единицы измерения:

var length = 10m  // 10 meters

var work = 5kg * 9.8 m/s/s * 10m
print( work )  // prints 490 J

var investment = 5000 EUR + 10000 USD

var date = 1966-May-5 2:35:53:909 PM PST