BinaryOp("+",
Ref("b"),
BinaryOp("*",
Literal(4),
UnaryOp("++", true, // true означает что оператор префиксный
Ref("d"))))
Компилятор, построение дерева, пост-пре-фиксный инкремент
пишу компилятор, такой 1 раз в жизни, раньше писал простой без всяких наворотов подобных в c++ .
объясню суть работы: за один проход обрабатываю скан лексем (flex), парсинг (bison) и семантику (в моем языке типы автоматически преобразуются)
результат разбора - ориентированный граф
первый вопрос:
предложите варианты проверки (семантика) находится ли break в цикле, есть свои варианты, но думаю, что существуют более эффективнее
второй вопрос:
проблема с инкрементами:
например префиксный инкремент (++b), как лучше его положить в дерево (ориентированный граф)? например, пример: b+4*++d
ведь не разумно в узлах ветки* ложить вторым аргументом еще один узел унарного оператора (++d) ведь нужно d увеличить на 1, или как быть с b++, в общем скажите плз, как их лучше положить в дерево )
объясню суть работы: за один проход обрабатываю скан лексем (flex), парсинг (bison) и семантику (в моем языке типы автоматически преобразуются)
результат разбора - ориентированный граф
первый вопрос:
предложите варианты проверки (семантика) находится ли break в цикле, есть свои варианты, но думаю, что существуют более эффективнее
второй вопрос:
проблема с инкрементами:
например префиксный инкремент (++b), как лучше его положить в дерево (ориентированный граф)? например, пример: b+4*++d
ведь не разумно в узлах ветки* ложить вторым аргументом еще один узел унарного оператора (++d) ведь нужно d увеличить на 1, или как быть с b++, в общем скажите плз, как их лучше положить в дерево )
Цитата: NSDaler
за один проход обрабатываю скан лексем (flex), парсинг (bison) и семантику (в моем языке типы автоматически преобразуются)
результат разбора - ориентированный граф
результат разбора - ориентированный граф
Это порочный путь. Удобнее всего разобрать исходник и построить AST - синтаксическое дерево, над которым впоследствии производить различные операции (связывание типов, контроль имен и прочее).
Цитата: NSDaler
первый вопрос:
предложите варианты проверки (семантика) находится ли break в цикле, есть свои варианты, но думаю, что существуют более эффективнее
Обходим рекурсивно AST и при входе в узел, соответствующий циклу, выставлять флаг "мы в цикле". При нахождении оператора break смотреть на этот флаг.
Цитата: NSDaler
второй вопрос:
проблема с инкрементами:
например префиксный инкремент (++b), как лучше его положить в дерево (ориентированный граф)? например, пример: b+4*++d
Для унарных операторов нужно ввести отдельный узел. Для примера "b+4*++d" дерево может быть следующим:
Код:
З.Ы. Я бы не стал использовать любых клонов lex+yacc. Мы сделали гораздо более удобную штуку - Nemerle.Peg. Вот пример парсера C# 4.0, там же по ссылке лежат AST C# и парсер для препорцессора.
это все понятно)) я так и сделал вы построили дерево, но инкремент можно сказать частный случай унарных операторов). вот смотрите:
UnaryOp("++", true) когда будем обрабатывать дерево и найдем узел ++ нам нужно увеличить на 1 идентификатор, то есть мы должны каким-то образом узнать начало выражения и перед ним поставить вроде того inc #id или наоборот оператор постфиксный тогда проблем еще больше, когда выйдем из узлов, откуда нам знать, что он последний в выражении и поставить инкремент, также проблема, когда префиксный инкремент каким-то образом вынесли перед выражением, то как нам решить проблему уже с прочитанными узлами, то есть выражение b = d * 6 + 4 * ++d, первый узел оператора+ прочитали и d идентификатор получил какое-то имя(адрес), дальше нашли еще узел, а там префиксный инкремент, как мы сможем повлиять на уже прочитанный узел и что-то изменить...
придумал такой принцип работы, на стадии парсинга нашли оператор префиксный ++ добавили его в очередь, когда начали сворачивать правило, отвечающее за все выражение, вытаскиваем из очереди...
может существует другой способ, еще эффективнее?
UnaryOp("++", true) когда будем обрабатывать дерево и найдем узел ++ нам нужно увеличить на 1 идентификатор, то есть мы должны каким-то образом узнать начало выражения и перед ним поставить вроде того inc #id или наоборот оператор постфиксный тогда проблем еще больше, когда выйдем из узлов, откуда нам знать, что он последний в выражении и поставить инкремент, также проблема, когда префиксный инкремент каким-то образом вынесли перед выражением, то как нам решить проблему уже с прочитанными узлами, то есть выражение b = d * 6 + 4 * ++d, первый узел оператора+ прочитали и d идентификатор получил какое-то имя(адрес), дальше нашли еще узел, а там префиксный инкремент, как мы сможем повлиять на уже прочитанный узел и что-то изменить...
придумал такой принцип работы, на стадии парсинга нашли оператор префиксный ++ добавили его в очередь, когда начали сворачивать правило, отвечающее за все выражение, вытаскиваем из очереди...
может существует другой способ, еще эффективнее?
Операторы как правило имеют приоритеты, их можно задавать явно и использовать алгоритм Pratt-парсера, он позволяет крайне быстро группировать выражения, либо эти приоритеты задаются парсером. В упомянутом выше парсере C#, используется комбинрованный подход - приоритеты бинарных операторов разруливаются классическим алгоритмом Pratt-а (эта самая ваша очередь), а унарные операторы - на уровне правил парсера:
Такая комбинация правил приведет к тому, что унарный оператор всегда к чему-то да отнесется :)
PS Вот моя реализация этой "очереди" с ее помощью распихиваются приоритеты бинарных операторов (числа - это левые и правые приоритеты):
Код:
prefixOperator = "++" / "--" / "+" / "-" / "~" / "!";
prefixExpression = prefixOperator postfixExpression;
postfixOperator = "++" / "--";
postfixExpression = someOtherExpr postfixOperator*;
prefixExpression = prefixOperator postfixExpression;
postfixOperator = "++" / "--";
postfixExpression = someOtherExpr postfixOperator*;
Такая комбинация правил приведет к тому, что унарный оператор всегда к чему-то да отнесется :)
PS Вот моя реализация этой "очереди" с ее помощью распихиваются приоритеты бинарных операторов (числа - это левые и правые приоритеты):
Код:
#region Binary operators
//binaryOperator : BinaryOperatorInfo = ("??" / "||" / "|" / "&&" / "&" / "==" / "!=" / "<=" / "<<" / "<"
// / ">=" / ">>" / ">" / "*" / "/" / "%" / "+" / "-" / "^")s;
binaryOperator(op : NToken) : Identifier * int * int
{
def opStr = GetText(op);
def opId = Identifier(GetLocation(op), opStr);
match(opStr) {
| "??" => (opId, 11, 10) // right associative
| "||" => (opId, 20, 20)
| "|" => (opId, 40, 40)
| "&&" => (opId, 30, 30)
| "&" => (opId, 60, 60)
| "==" => (opId, 70, 70)
| "!=" => (opId, 70, 70)
| "<=" => (opId, 80, 80)
| "<<" => (opId, 90, 90)
| "<" => (opId, 80, 80)
| ">=" => (opId, 80, 80)
| ">>" => (opId, 90, 90)
| ">" => (opId, 80, 80)
| "*" => (opId, 110, 110)
| "/" => (opId, 110, 110)
| "%" => (opId, 110, 110)
| "+" => (opId, 100, 100)
| "-" => (opId, 100, 100)
| "^" => (opId, 50, 50)
| _ => throw ArgumentOutOfRangeException("op")
}
}
//typeTestingOperator : BinaryOperatorInfo = ("is" / "as")S;
typeTestingOperator(op : NToken) : Identifier * int * int
{
(Identifier(GetLocation(op), GetText(op)), 70, 200)
}
//binaryOperatorExpression : Expr = prefixExpression ( (binaryOperator prefixExpression) / (typeTestingOperator anyTypeNullableHack) )*;
binaryOperatorExpression( head : Expr,
tail : SCG.List[(Identifier * int * int) * Expr]) : Expr
{
match(tail.Count) {
| 0 => head
| 1 =>
def a = head;
def ((op, _, _), b) = tail[0];
Expr.BinaryOperator(a.Location + b.Location, a, b, op)
| _ =>
def opStack = SCG.Stack();
def exprStack = SCG.Stack();
exprStack.Push(head);
def evalOperandsOnStack() {
def b = exprStack.Pop();
def a = exprStack.Pop();
def op = opStack.Pop()[0];
exprStack.Push(Expr.BinaryOperator(a.Location + b.Location, a, b, op));
}
foreach(((op, leftPrior, rightPrior), operand) in tail) {
when (!opStack.IsEmpty() && opStack.Peek()[1] >= leftPrior)
evalOperandsOnStack();
exprStack.Push(operand);
opStack.Push(op, rightPrior);
}
while(!opStack.IsEmpty())
evalOperandsOnStack();
exprStack.Pop() // exprStack becomes empty
}
}
#endregion
//binaryOperator : BinaryOperatorInfo = ("??" / "||" / "|" / "&&" / "&" / "==" / "!=" / "<=" / "<<" / "<"
// / ">=" / ">>" / ">" / "*" / "/" / "%" / "+" / "-" / "^")s;
binaryOperator(op : NToken) : Identifier * int * int
{
def opStr = GetText(op);
def opId = Identifier(GetLocation(op), opStr);
match(opStr) {
| "??" => (opId, 11, 10) // right associative
| "||" => (opId, 20, 20)
| "|" => (opId, 40, 40)
| "&&" => (opId, 30, 30)
| "&" => (opId, 60, 60)
| "==" => (opId, 70, 70)
| "!=" => (opId, 70, 70)
| "<=" => (opId, 80, 80)
| "<<" => (opId, 90, 90)
| "<" => (opId, 80, 80)
| ">=" => (opId, 80, 80)
| ">>" => (opId, 90, 90)
| ">" => (opId, 80, 80)
| "*" => (opId, 110, 110)
| "/" => (opId, 110, 110)
| "%" => (opId, 110, 110)
| "+" => (opId, 100, 100)
| "-" => (opId, 100, 100)
| "^" => (opId, 50, 50)
| _ => throw ArgumentOutOfRangeException("op")
}
}
//typeTestingOperator : BinaryOperatorInfo = ("is" / "as")S;
typeTestingOperator(op : NToken) : Identifier * int * int
{
(Identifier(GetLocation(op), GetText(op)), 70, 200)
}
//binaryOperatorExpression : Expr = prefixExpression ( (binaryOperator prefixExpression) / (typeTestingOperator anyTypeNullableHack) )*;
binaryOperatorExpression( head : Expr,
tail : SCG.List[(Identifier * int * int) * Expr]) : Expr
{
match(tail.Count) {
| 0 => head
| 1 =>
def a = head;
def ((op, _, _), b) = tail[0];
Expr.BinaryOperator(a.Location + b.Location, a, b, op)
| _ =>
def opStack = SCG.Stack();
def exprStack = SCG.Stack();
exprStack.Push(head);
def evalOperandsOnStack() {
def b = exprStack.Pop();
def a = exprStack.Pop();
def op = opStack.Pop()[0];
exprStack.Push(Expr.BinaryOperator(a.Location + b.Location, a, b, op));
}
foreach(((op, leftPrior, rightPrior), operand) in tail) {
when (!opStack.IsEmpty() && opStack.Peek()[1] >= leftPrior)
evalOperandsOnStack();
exprStack.Push(operand);
opStack.Push(op, rightPrior);
}
while(!opStack.IsEmpty())
evalOperandsOnStack();
exprStack.Pop() // exprStack becomes empty
}
}
#endregion