Comments (32)
here is cpp's operator precedence https://en.cppreference.com/w/cpp/language/operator_precedence im pretty sure its common sense using bidmas i can help if need be.
from one.
Another nice example from PEG.JS
:
// Simple Arithmetics Grammar
// ==========================
//
// Accepts expressions like "2 * (3 + 4)" and computes their value.
Expression
= head:Term tail:(_ ("+" / "-") _ Term)* {
return tail.reduce(function(result, element) {
if (element[1] === "+") { return result + element[3]; }
if (element[1] === "-") { return result - element[3]; }
}, head);
}
Term
= head:Factor tail:(_ ("*" / "/") _ Factor)* {
return tail.reduce(function(result, element) {
if (element[1] === "*") { return result * element[3]; }
if (element[1] === "/") { return result / element[3]; }
}, head);
}
Factor
= "(" _ expr:Expression _ ")" { return expr; }
/ Integer
Integer "integer"
= _ [0-9]+ { return parseInt(text(), 10); }
_ "whitespace"
= [ \t\n\r]*
from one.
A = (2 + 15 * ( 25 - 13 ) / 1 - 4) + 10 / 2
AST TREE of The above mathematic expression:
[EXPR] +
Left:
[EXPR] +
Left:
[EXPR] VALUE 2
Right:
[EXPR] *
Left:
[EXPR] VALUE 15
Right:
[EXPR] /
Left:
[EXPR] -
Left:
[EXPR] VALUE 25
Right:
[EXPR] VALUE 13
Right:
[EXPR] -
Left:
[EXPR] VALUE 1
Right:
[EXPR] VALUE 4
Right:
[EXPR] /
Left:
[EXPR] VALUE 10
Right:
[EXPR] VALUE 2
I'm not sure it's correct or no.
It's wrong. but what is correct? so....
A = (2 + 15 * (( 25 - 13 ) / 1) - 4) + 10 / 2
A = (2 + (15 * ( 25 - 13 ) / 1) - 4) + 10 / 2
or ?
from one.
Thanks from https://github.com/carlos-chaguendo/arboles-binarios
from one.
Thank you for your message.
Okay, honestly I not sure about some special operators. such as >> << and etc.
I aware Operator-precedence is different in every language. So I not sure how we can go up.
I think we can figure out how PHP works by thinking about its Operator-precedence parser.
- https://github.com/php/php-src/blob/master/Zend/zend_language_scanner.l
- https://github.com/php/php-src/blob/master/Zend/zend_language_parser.y
from one.
I checked its parser. They did not divide the phrase into several groups.
And he manages these using BISON. https://github.com/php/php-src/blob/master/Zend/zend_language_parser.y#L1041
Since we are writing Parser by hand, we need to group and know more details.
- https://www.tutorialspoint.com/cprogramming/c_operators_precedence.htm
- https://en.cppreference.com/w/c/language/operator_precedence
from one.
Dear @snapogod;
#71 (comment)
Can you help us complete the BNF grammar? https://github.com/One-Language/One/blob/master/grammar.BNF
We need to know grammar of all operators.
from one.
Another nice implementation of the expression parser. But it does not help us much.
https://github.com/maxicombina/c-calculator/blob/master/calculator.c#L170
int get_op_precedence(char op)
{
int res = 0;
if (op == '+' || op == '-')
{
res = 9;
}
else if (op == '*' || op == '/' || op == '%')
{
res = 10;
}
else if (op == '^')
{
res = 11;
}
return res;
}
static int is_higher_or_equal_precedence(char op1, char op2)
{
return get_op_precedence(op1) >= get_op_precedence(op2);
}
static int is_higher_precedence(char op1, char op2)
{
return get_op_precedence(op1) > get_op_precedence(op2);
}
static int is_left_assoc_operator(char op)
{
return (op == '+' || op == '-' || op == '*' || op == '/' || op == '%');
}
static int is_right_assoc_operator(char op)
{
return (op == '^');
}
from one.
Some useful references I find yesterday:
https://depositonce.tu-berlin.de/bitstream/11303/2630/1/Dokument_46.pdf
https://cdn2.hubspot.net/hubfs/3881487/ExprParser_User_Guide.pdf?t=1517563829446
from one.
Another nice implementation of the expression parser:
https://github.com/programoworm/Expression_Recogniser/blob/master/expression.c
This is something I extracted from the above code but it is still incomplete and has a problem:
parseFactor = "+" parseFactor # need Fix
= "-" parseFactor # need Fix
= "(" INT ")"
= INT
parseTerm = parseFactor
= parseFactor "*" parseFactor
= parseFactor "/" parseFactor
parseExpressions = parseTerm
= parseTerm "+" parseTerm
= parseTerm "-" parseTerm
from one.
I found some online tools that can test grammar.
This is very interesting and it is better to test the grammars in the same way.
More about this subject:
- http://www.nongnu.org/bnf/
- https://github.com/codelion/gramtest
- https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/
But I'm looking for something that can draw a picture and show it with a figure ... Do you know anything?
from one.
The above codes are summarized as follows:
Expression = Term ( ("+" / "-") Term)*
| Term
Term = Factor ( ("*" / "/") Factor)*
Factor = "(" Expression ")"
| [0-9]+
The problem is that this grammar is not complete and does not include dozens of operators!
from one.
A tiny YACC/Bison example:
exp: exp OPERATOR_PLUS exp
| exp OPERATOR_MINUS exp
| exp OPERATOR_MULT exp
| exp OPERATOR_DIV exp
| LPAREN exp RPAREN
| NUMBER
https://www.cs.uic.edu/~spopuri/ibison.html
from one.
Okay, so again we need "Precedence of operators in BNF grammar" with all operators not only + - * /.
from one.
And finally, I find BNF of c language:
https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm
And also another nice documentation for BNF:
https://www.radford.edu/~nokie/classes/380/syntax.html
from one.
=============== INPUT ===============
package main
i8 test1 {
_ 4
_ 5+1
}
=============== TREE ===============
Package: main
[FUNC] test1
[STMT] PRINT
[EXPRESSIONS] 1 expression(s)
[EXPR] VALUE 4
[STMT] PRINT
[EXPRESSIONS] 1 expression(s)
[EXPR] +
Left:
[EXPR] VALUE 5
Right:
[EXPR] VALUE 1
=============== VM ===============
Package: main
[FUNC] test1
[STMT] PRINT
[STMT] PRINT
Currently + - operators supported. But we need to add many more operators.
A question, The input is _ 5+1-2+6
generate this TREE:
[STMT] PRINT
[EXPRESSIONS] 1 expression(s)
[EXPR] +
Left:
[EXPR] VALUE 5
Right:
[EXPR] -
Left:
[EXPR] VALUE 1
Right:
[EXPR] +
Left:
[EXPR] VALUE 2
Right:
[EXPR] VALUE 6
It's correct? can someone check this?
from one.
A message from Dear snappyagggodypingable:
a = b
a += b
a -= b
a *= b
a /= b
a %= b
a &= b
a |= b
a ^= b
a <<= b
a >>= b
++a
--a
a++
a--
+a
-a
a + b
a - b
a * b
a / b
a % b
~a
a & b
a | b
a ^ b
a << b
a >> b
!a
a && b
a || b
a == b
a != b
a < b
a > b
a <= b
a >= b
a <=> b
a[b]
a
&a
a->b
a.b
a->b
a.*b
all those right?
from one.
ruby:
<=> == === != =~ !~
= %= { /= -= += |= &= >>= <<= *= &&= ||= **=
And again message from Dear snappyagggodypingable:
<expression> ::= <term> "+" <expression>
| <term> "-" <expression>
| <term>
<term> ::= <factor> "*" <term>
| <factor> "/" <term>
| <factor>
<power> ::= <factor> ^ <power>
| <factor>
<factor> ::= "(" <expression> ")"
| <const>
<const> ::= NUMBER | STRING | IDENTIFIER
from one.
Hooray, It's mostly done and now works. 👍
I did used C operators table: https://en.cppreference.com/w/c/language/operator_precedence
from one.
Correct answer is:
= (2 + ((15 * (25 - 13)) / 1) - 4) + (10 / 2)
from one.
Below is the full implementation of EvaluateExpression function and its helpers in C#.
int EvaluateExpression(char[] exp)
{
Stack<int> vStack = new Stack<int>();
Stack<char> opStack = new Stack<char>();
opStack.Push('('); // Implicit opening parenthesis
int pos = 0;
while (pos <= exp.Length)
{
if (pos == exp.Length || exp[pos] == ')')
{
ProcessClosingParenthesis(vStack, opStack);
pos++;
}
else if (exp[pos] >= '0' && exp[pos] <= '9')
{
pos = ProcessInputNumber(exp, pos, vStack);
}
else
{
ProcessInputOperator(exp[pos], vStack, opStack);
pos++;
}
}
return vStack.Pop(); // Result remains on values stacks
}
void ProcessClosingParenthesis(Stack<int> vStack,
Stack<char> opStack)
{
while (opStack.Peek() != '(')
ExecuteOperation(vStack, opStack);
opStack.Pop(); // Remove the opening parenthesis
}
int ProcessInputNumber(char[] exp, int pos,
Stack<int> vStack)
{
int value = 0;
while (pos < exp.Length &&
exp[pos] >= '0' && exp[pos] <= '9')
value = 10 * value + (int)(exp[pos++] - '0');
vStack.Push(value);
return pos;
}
void ProcessInputOperator(char op, Stack<int> vStack,
Stack<char> opStack)
{
while (opStack.Count > 0 &&
OperatorCausesEvaluation(op, opStack.Peek()))
ExecuteOperation(vStack, opStack);
opStack.Push(op);
}
bool OperatorCausesEvaluation(char op, char prevOp)
{
bool evaluate = false;
switch (op)
{
case '+':
case '-':
evaluate = (prevOp != '(');
break;
case '*':
case '':
evaluate = (prevOp == '*' || prevOp == '');
break;
case ')':
evaluate = true;
break;
}
return evaluate;
}
void ExecuteOperation(Stack<int> vStack,
Stack<char> opStack)
{
int rightOperand = vStack.Pop();
int leftOperand = vStack.Pop();
char op = opStack.Pop();
int result = 0;
switch (op)
{
case '+':
result = leftOperand + rightOperand;
break;
case '-':
result = leftOperand - rightOperand;
break;
case '*':
result = leftOperand * rightOperand;
break;
case '':
result = leftOperand rightOperand;
break;
}
vStack.Push(result);
}
from one.
LexAndYacc.pdf
OperatorPrecedenceParsing.pdf
from one.
Great work @BaseMax !! 🥇
from one.
Hey @BaseMax what is the status of this issue ?
from one.
A new update: almost every operator work well in the new version. We are on a roll!
Happy ^_^
from one.
_ (2 + 15 * ( 25 - 13 ) / 1 - 4) + 10 / 2
Tree Output of the expression:
└──Statement: PRINT
└──Expressions (1)
└──Expression +
└──Expression Left
└──Expression -
└──Expression Left
└──Expression +
└──Expression Left
└──Expression Direct: 2
└──Expression Right
└──Expression *
└──Expression Left
└──Expression Direct: 15
└──Expression Right
└──Expression /
└──Expression Left
└──Expression -
└──Expression Left
└──Expression Direct: 25
└──Expression Right
└──Expression Direct: 13
└──Expression Right
└──Expression Direct: 1
└──Expression Right
└──Expression Direct: 4
└──Expression Right
└──Expression /
└──Expression Left
└──Expression Direct: 10
└──Expression Right
└──Expression Direct: 2
I not sure it's correct or no.
from one.
That was wrong. I fixed bug 4c07353.
and finally it's AST output:
└──Statement: PRINT
└──Expressions (1)
└──Expression +
└──Expression Left
└──Expression -
└──Expression Left
└──Expression +
└──Expression Left
└──Expression Direct: 2
└──Expression Right
└──Expression /
└──Expression Left
└──Expression *
└──Expression Left
└──Expression Direct: 15
└──Expression Right
└──Expression -
└──Expression Left
└──Expression Direct: 25
└──Expression Right
└──Expression Direct: 13
└──Expression Right
└──Expression Direct: 1
└──Expression Right
└──Expression Direct: 4
└──Expression Right
└──Expression /
└──Expression Left
└──Expression Direct: 10
└──Expression Right
└──Expression Direct: 2
from one.
Sorry, I don't have much time to translate this to English:
مثلا جمع و تفریق بنظر چپ به راست هست.
5 + 4
5 - 4
ضرب و تقسیم هم همینطور چپ به راست هست.
5 * 4
اما مساوی راست به چپ هست.
a = 5+4
حتی کوچک تر / بزرگتر/ کوچکتر مساوی / بزرگتر مساوی هم چپ به راست هست.
5 > 4
5 < 4
یکسری مثال خوب و شفاف پیدا کردم میفرستم شاید بدرد شما هم بخوره.
سعی میکنم تحلیل کنم نتیجه برسم
Example: 5 - 4 - 3
(5 - 4) - 3 = -2 // left association is correct
5 - (4 - 3) = 4 // right is incorrect
Example: x = y = z
x = (y = z) // right association is correct, sets x and y
(x = y) = z // left is incorrect, does not set y
این دقیقا بحث operator associativity هست که نمیدونم فارسی اش چیه:
https://en.wikipedia.org/wiki/Operator_associativity
سلام.
درسته. مثلا این عبارت:
100 / 10 * 10
برابر هست با:
(100/10) * 10
= 10 * 10
چون بنظر عملگر ضرب و تقسیم هر دو چپ به راست هستند.
اما وقتی عبارت پیچیده میشه گیج میشم نمیفهمم چی به چی باید بشه از کجا شروع کنم.
:
5 + 100 / 10 * 10 = 10/2 * 5 - 1
اول اینکه جمع و تفریق چپ به راست هست.
ضرب تقسیم هم چپ به راست هست.
ولی تساوی راست به چپ هست. علت اش رو نمیدونم ولی با این فرض سعی میکنم ادامه دهم:
105 / 10 * 10 = 10/2 * 5 -1
در مرحله بعدی سعی میکنم تقسیم سمت چپ رو حل کنم. اصلا چرا باید از سمت چپ شروع کنیم؟ چرا از سمت راست شروع نمیکنیم؟ مگر ما اینجا تساوی هم نداریم تساوی از راست به چپ هست. ولی بنظر ما باید طبق قانونی که معلوم نیست چیه از چپ شروع به تحلیل کنیم.
10.5 * 10 = 10/2 * 5 -1
و حالا اگر دوباره ادامه دهیم و ضرب سمت چپ رو هم حساب کنیم:
105 = 10/2 * 5 -1
حالا به اینجا رسیدیم که سمت چپ تساوی یک جواب نهایی داریم. و حالا که به تساوی برخورد میکنیم. میرویم که طرف دیگه رو تحلیل کنیم:
105 = 5 * 5 -1
و حالا ضرب سمت راست رو تحلیل کنیم:
105 = 25 -1
و حالا تفریق سمت راست:
105 = 24
و این شد جواب اخر. درسته این دو تا برابر نیستند لزومی هم نبوده برابر باشند. صرفا یه عبارت ریاضی هست که ممکنه درست باشه یا نه.
توی این تحلیل من اصلا هیچ موردی توی ذهنم رو برای عملگر مساوی رعایت نکردم چون عملگر مساوی راست به چپ هست اما تغییری برام ایجاد نکرد یا حداقل بلد نیستم چه تغییری ایجاد کرده که نفهمیدم.
These thoughts were in my mind.
from one.
عبارت ریاضی:
دو تحلیل مختلف که میشود داشت:
یکی از راست:
اها. الان بیشتر متوجه میشوم. مثلا اگه همچین عبارتی داشته باشیم:
! ( + ( -(X) ) )
خب مشخص هست که هنوز نفهمیدم چون گیر میکنم.
الان چه دلیلی داره که میگویند عملگر ! که قبل از چیزی میاد راست به چپ هست. و چرا چپ به راست نیست؟
نمیدونم حالتی که چپ به راست میشه رو چطور و چی باید نوشت
from one.
سعی کردم یه عبارت ریاضی سخت تر و پیچیده بسازم:
from one.
It's fixed in new version, I have to push new version and focus on the core.
from one.
Do you have an update on this ? Is core ready in the new branch ?
from one.
Related Issues (20)
- gha: check Markdown links: https://www.instagram.com/one.lang → Status: 429
- 🪪 Change License template 🪪
- ❔ Auto run pre-commit on top of Git ❔ HOT 2
- 🔗 We need a much better link for "Getting Started" 🔗 HOT 2
- 📦 Only `Dockerize` if Docker files change on merge to main 📦 HOT 3
- 🏗️ Fix Docker Build 🏗️
- Forks should not Dockerize HOT 1
- 🎨 Change Formatting 🎨 HOT 3
- Configure link checker for twitter links HOT 1
- Add `markdown-link-check` to `pre-commit` HOT 2
- We need to update `CONTRIBUTORS.md` HOT 7
- 🛂 Need to review `CONTRIBUTING.md` 🛂
- ✅ Super-Linter add editorconfig-checker ✅
- 🧪 Current pre-commit requirements and enhancements 🧪 HOT 3
- 🐛 First Interaction GitHub Action Error 🐛 HOT 3
- [Join] Core team HOT 1
- Pull request labeler is broken HOT 1
- 📃 Add the "Contributors" section from the English README to all READMEs 📃
- Errors found in GITHUB_ACTIONS
- 🐛 Super-Linter - HTML errors 🐛 HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from one.