How to copy an expression programmatically?

Question

I have an idea for a simple program that will help me with operator precedence in languages ​​like C. The most difficult part of this is enclosing the expression in parentheses. For example, I want this:

*a.x++ = *b.x++ 

Converted to this:

 ((*(((a).(x))++)) = (*(((b).(x))++))) 

What I did manually in the following steps:

  *a.x++ = *b.x++ *(a).(x)++ = *(b).(x)++ *((a).(x))++ = *((b).(x))++ *(((a).(x))++) = *(((b).(x))++) (*(((a).(x))++)) = (*(((b).(x))++)) ((*(((a).(x))++)) = (*(((b).(x))++))) 

What is the best way to do this programmatically? Is there a solution that I could use? I would prefer to do this in PHP, C, C ++, Python or Ruby.

(This is not the whole idea of ​​my program, this is just the first step.)

Answer 1

Just pick up the parser for your chosen language, for example C parser , parse the expression / source code and print the AST back to whatever you want.

test.c:

 void main(void){ int c = 2; } 

Terminal:

 $ python >>> import pycparser >>> test = pycparser.parse_file('test.c') >>> test.show() FileAST: FuncDef: Decl: main, [], [] FuncDecl: ParamList: Typename: [] TypeDecl: None, [] IdentifierType: ['void'] TypeDecl: main, [] IdentifierType: ['void'] Compound: Decl: c, [], [] TypeDecl: c, [] IdentifierType: ['int'] Constant: int, 2 >>> for node in test.ext: ... print node ... <pycparser.c_ast.FuncDef object at 0x7fe1436db750> >>> 

Answer 2

You will need some kind of parser that understands the accuracy of the operator. The usual version for C is Lexx / Yacc or flex / bison, and the easiest way to do this is to build a parse tree. Once you do this, just go through the parse tree in preorder order and emit parens when you enter and leave node.

Answer 3

The most reliable way is to parse the expression (taking into account the priority rule ), and then process the resulting AST (abstract syntax tree) from top to bottom, adding brackets as you move along

Answer 4

How about postfix conversion and evaluation. Can you try if the following approach works. Take * ax ++

 Operator Precedence Arguments Needed . 3 2 ++ 2 1 * 1 1 

So now we transform the expression into postfix notation. That should give you

 ax . ++ * 

Now evaluating the postfix is ​​as simple as pushing things onto the stack when you click on an operator, select the top elements of n (as necessary by the operator) and pass them as arguments, save the results back to the stack. In your case, instead of evaluating, you will return a textual representation of the operation

  Stack Read aa Read xx Read . (ax) Read ++ ((ax)++) Read * (*((ax)++)) 

if this helps, you can see:
http://www.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
Bart de smet DynCalc Publication Series
My attempt at TDDing a similar solution

Answer 5

You can create a binary expression tree from statements.

I believe that there are currently several algorithms available to create such a tree.

One simple way I could think of is to sort the operator by priority, and then split the line into two parts by the operator with the lowest priority first, and then continue to recursively split the remaining 2 parts down again and again, and then in the end, you get the expression in the form of a binary tree.

And then, when you have the binary expression of the tree, you can “parenthesize” from the tree left to the root.

And, of course, you can compile a full-fledged parser through yacc / bison.

Answer 6

As a simple example:

 Exp = Term | Exp, AddOp, Term Term = Factor | Term, MulOp, Factor Factor = Number | Ident | PreOp, Factor | (, Exp, ) | Factor, PostOp 

You can use grammar to write translations:

 Exp = Term -> Term | Exp, AddOp, Term -> (, Exp, AddOp, Term, ) Term = Factor -> Factor | Term, MulOp, Factor -> (, Term, MulOp, Factor, ) Factor = Number -> Number | Ident -> Ident | PreOp, Factor -> (, PreOp, Factor, ) | (, Exp, ) -> (, Exp, ) | Factor, PostOp -> (, Factor, PostOp, ) 

In this case:

 a-- + b * (a+b) 

Translated to:

 ((a--) + (b * ((a+b)))) 

Answer 7

Parsing is a huge topic. Because you just want to use it to solve a specific problem, try not to dive into all of these specific parsing algorithms that people offer. Rather, there are numerous parser generators, such as antler or bison, which, given the appropriate grammar, will parse the text and allow you to perform programmatic operations on components - for example, put parentheses around them. Some of these systems come with or have grammars for C.

antlr can generate parsers in any of the languages ​​you mention; see http://www.antlr.org/

Answer 8

You can find "cparen" in the archives of the old net.sources newsgroup.

If you search (Google) for 'cparen', you get too much noise, but if you do a search for net.sources and 'cparen.c', which narrows the search enough to be useful.

Here is one website:

http://www.megalextoria.com/usenet-archive/news005f3/b14/net/sources/00000360.html

This is not a shell archive, as I expected. It looks like a plain ASCII text tar file. Quite a few files that you could just unzip it manually.

Answer 9

I wrote a program in Python to insert an expression string.

 def pref(op): print "called with op", op ret = -1 if op == '+': print "matched +" ret = 1 if op == '-': print "matched -" ret = 2 if op == '*': print "matched *" ret = 3 if op == '/': print "matched /" ret = 4 return ret def evaluate(expr, operand_stack, operator_stack): print "**In evaluate**" print operator_stack print operand_stack expr1 = operand_stack.pop() expr2 = operand_stack.pop() op = operator_stack.pop() # Parenthesize the expression expr = "(" + expr2 + op + expr1 + ")" print "expr1", expr1 print "expr2", expr2 print "expr", expr # Push the result back on the stack operand_stack.append(expr) print operator_stack print operand_stack print "**Out evaluate**" return expr def looper(str, expr, operator_stack, operand_stack): l = 0 cnt = len(str) # Loop over the input string while l < cnt: if str[l] in ('+', '-', '*', '/'): print "operator found: op, index", str[l], l print operator_stack, len(operator_stack) x = len(operator_stack) - 1 if x > 0: print "Comparing:", operator_stack[x], str[l] # If op on stack has higher preference than the op in question if (pref(operator_stack[x]) > pref(str[l])): expr = evaluate(expr, operand_stack, operator_stack) operator_stack.append(str[l]) else: # Add the operand to operand stack operand_stack.append(str[l]) l += 1 print operator_stack print operand_stack print "Take care of last elements" op_cnt = len(operator_stack) while op_cnt: expr = evaluate(expr, operand_stack, operator_stack) op_cnt -= 1 print operator_stack print operand_stack if __name__ == '__main__': str = "a+c*de/w*x+as" cnt = len(str) operand_stack = [] operator_stack = [] expr = "" looper(str, expr, operator_stack, operand_stack) print "Output=>", operand_stack[0] 

Answer 10

There is a very old (1980s) open source program to do just that. It's called cparen, but I'm damned if I find it online. Only enthusiastic references to this, for example. https://groups.google.com/group/comp.lang.c/tree/browse_frm/month/1990-03/1583b4728a6d94db http://www.language-c.info/re-should-i-capitalize-const -identifiers

If you have more luck than in the search, write