Basi c вопросов по маневровой станции

Question

Я завершил реализацию алгоритма Shunting-yard, но у меня есть несколько вопросов:

1. Как этот алгоритм проверяет правильность ввода, другими словами, как он может определить, что + + b допустимо или нет (конечно, нет)

2. Какой второй шаг мне следует сделать? Маневровая площадка конвертирует 1+2 в 1 2 +

Обновление относительно 1:

После некоторых попыток я думаю, что да. Например, возьмите a++b, это будет a+b+, тогда, когда я его оцениваю, я бы взял then + но поскольку у меня есть только одна переменная, это ошибка.

Всегда ли это так Для недействительных выражений?

Answer 1

1. Синтаксические ошибки

Это зависит от того, как именно вы реализуете алгоритм, но в версии, обычно обнаруживаемой при поиске inte rnet, нет гарантии, что неграмматическое выражение будет правильно отклонено алгоритмом маневрового двора. . Многие неправильные выражения приводят к неправильным строкам постфикса (как вы заметили) или даже правильным строкам постфикса. В частности, если у вас есть унарные операторы, алгоритм (как обычно представлен) не может действительно различать использование префикса, когда оператор предшествует операнду, или использование постфикса, когда оператор следует за операндом.

Это будет серьезная проблема, если в вашем целевом языке есть операторы, которые могут использоваться как префиксные или постфиксные операторы с разной семантикой (например, операторы ++ и -- семейства C). Поскольку алгоритм не различает guish два случая, семанти c разница теряется.

Есть похожая, более распространенная проблема с операторами, которые могут использоваться либо как двоичные инфиксные операторы, либо как префиксные операторы, такие как оператор -. Если эти два использования не различаются, вывод постфикса не будет интерпретируемым, потому что при достижении - оценщик не может знать, применимо ли оно к одному или двум операндам. (Кроме того, вполне вероятно, что оператор унарного минуса будет обработан с неправильным приоритетом, поскольку желаемый приоритет унарного минуса выше, чем умножение и деление. Однако для большинства выражений арифметики c использование неправильного приоритета не приведет к измените числовое значение c результата, поскольку -(x * y) и (-x) * y имеют точно такое же значение. Некорректные результаты будут очевидны, если вы реализуете оператор по модулю.)

Алгоритм маневрового двора обнаружит несбалансированные круглые скобки, потому что несбалансированные круглые скобки либо приведут к переполнению стека синтаксического анализа, либо к слишком большому количеству значений в конце синтаксического анализа.

Относительно легко дополнить алгоритм Shunting Yard с помощью очень маленького конечного автомата, достаточного для классификации различного однозначного использования операторов с более чем одним синтаксисом c значение; этого конечного автомата также достаточно для обнаружения других синтаксических ошибок, упомянутых выше: операторы неправильно размещены или вообще отсутствуют.

Потому что на практике необходимо правильно различать guish между унарным и двоичным отрицанием ; различное значение префиксных и постфиксных операторов; и различное использование круглых скобок (группировка по сравнению с вызовами функций), производственные парсеры, использующие Shunting Yard, будут включать некоторый дополнительный механизм syntacti c, который также будет обнаруживать синтаксические ошибки. Пример такого алгоритма можно найти в этом ответе .

2. RPN как промежуточный шаг

Нет никакой необходимости использовать RPN как промежуточный результат; алгоритм Shunting Yard может использоваться для

• прямой оценки арифметических c выражений (если выражения не включают условные конструкции или конструкции цикла),

• для вывода исполняемого кода для компилятора стековой машины (или, с немного большими усилиями, трехадресного кода для более реалистичной c машины), или в более общем смысле

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

Чтобы создать синтаксическое дерево, вам необходимо pu sh операндов в стек синтаксического анализатора, а не напрямую выводить их в выходной поток. Кроме того, когда вы помещаете sh оператор в стек, вы фактически создаете sh узел синтаксиса, представляющий приложение этого оператора: для бинарного оператора он объединяется с двумя верхними слотами стека. (А для унарного оператора с верхним слотом стека. ) Если вы хотите использовать маневровую площадку в качестве прямого оценщика, вы используете ту же стратегию, но нажатие оператора на стек вызывает вычисление этого оператора с его операндами, идентифицируемыми таким же образом. представление действительно не имеет никакой ценности. Понятия не имею, почему это так популярно.

Answer 2

давай посмотрим, смогу ли я сломать это для тебя. Алгоритм маневрового двора выполняет одно из следующих действий, нарушая инфиксную нотацию:

1. либо создает строку постфиксной нотации (также известную как нотация Reverse Poli sh)
2. или абстрактный синтаксис дерево.

В вашем случае это постфиксная нотация.

[примечание: я надеюсь, вы знаете о постфиксной нотации, если нет, то прочтите this .]

Теперь, постфиксная нотация позволяет очень легко вычислять математические выражения. Я покажу вам, как оценить постфиксную нотацию:

In a simple description:
    (1) Infix: A + B
        Postfix: A B +
    (2) Infix: A + B * C
        Postfix: A B C * +

Let's observe the part A+B*C i.e. A+(B*C)

If we represent it in Postfix, it would be like: A B C * +(by applying shunting-yard)

Now, the algorithm to calculate it
    (1) Take a stack
    (2) When we see a number, we push it to stack
    (3) When we see a operator, we pop two numbers out of stack and calculate them with help of operator and push the result into stack again
    (4) We do it till the end
    (5) At last, only a number would be left in stack, that is our answer.

Let's visualise it:
    (1) [A]
    (2) [A, B]
    (3) [A, B, C]
    (4) [A, R1] where R1 = B*C
    (5) [R2] where R2 = A+R1

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

Теперь вопрос в том, как обнаружить a++b ошибку :

Теперь посмотрите, что происходит для a, +, + , b токенов (как вы указали в комментарии: a++b - это токены a, +, +, b):

Я взял псевдокод из википедии (ленился, не хотел написать себя):

else if the token is an operator then:
        while ((there is a operator at the top of the operator stack)
              and ((the operator at the top of the operator stack has greater precedence)
               or (the operator at the top of the operator stack has equal precedence and the token is left associative))
              and (the operator at the top of the operator stack is not a left parenthesis)):
            pop operators from the operator stack onto the output queue.
        push it onto the operator stack.

в соответствии с этим: a, +, +, b будут иметь следующую форму в очереди вывода:

a, b, +, +

a, b, +, + просто неправильно , потому что, согласно правилам оценки постфикса, будет происходить следующее:

1. [a] // output queue is now [b, +, +]
2. [a, b] // output queue is now [+, +]
3. [r1] // output queue is now [+]
4. error // cause: notice there's still one '+' operator left in queue
// but, only one number 'r1' left in the 'stack'
// so, error

Надеюсь, теперь вам ясно ...