[PATCH olang v1] spec: ebnf: add binary expressions

[PATCH olang v1] spec: ebnf: add binary expressions

[Johnny Richard]

The parser already implements binary operations, but currently we are
missing it on the language specification.

This change adds the already implemented binary operations grammar and
also enables expression with parenthesis.  

It's important to mention that the precedence was highly inspired on C.

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
---

Ricardo, this is the missing spec I mentioned on your reply on variable
PATCH[1].  Let me know if this change make sense.

NOTE: This PATCH has been implemented on top of the commit mentioned
(base-commit) in the bottom of this PATCH.

[1]: Message-ID: <sm7jzr3mklfxscefg25cdhnrtjqldawquvgq6cdczi5kfyt4my@upgwv63nrzw7>

 docs/pages/language-specification.md | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

diff --git a/docs/pages/language-specification.md b/docs/pages/language-specification.md
index 4d0eb36..ff0a215 100644
--- a/docs/pages/language-specification.md
+++ b/docs/pages/language-specification.md
@@ -46,7 +46,22 @@ language.
 <return-statement>    ::= 'return' <ws> <expression>
 
 (* Expressions *)
-<expression>          ::= <integer> | <identifier>
+<expression>                ::= <binary-expression>
+<binary-expression>         ::= <logical-or-expression>
+<logical-or-expression>     ::= <logical-and-expression> (<ows> '||' <ows> <logical-and-expression>)*
+<logical-and-expression>    ::= <bitwise-or-expression> (<ows> '&&' <ows> <bitwise-or-expression>)*
+<bitwise-or-expression>     ::= <bitwise-xor-expression> (<ows> '|' <ows> <bitwise-xor-expression>)*
+<bitwise-xor-expression>    ::= <bitwise-and-expression> (<ows> '^' <ows> <bitwise-and-expression>)*
+<bitwise-and-expression>    ::= <cmp-eq-and-neq-expression> (<ows> '&' <ows> <cmp-eq-and-neq-expression>)*
+<cmp-eq-and-neq-expression> ::= <cmp-lt-and-gt-expression> (<ows> ('==' | '!=') <ows> <cmp-lt-and-gt-expression>)*
+<cmp-lt-and-gt-expression>  ::= <bitwise-shift-expression> (<ows> ('<' | '>') <ows> <bitwise-shift-expression>)*
+<bitwise-shift-expression>  ::= <additive-expression> (<ows> ('<<' | '>>') <ows> <additive-expression>)*
+<additive-expression>       ::= <multiplicative-expression> (<ows> ('+' | '-') <ows> <multiplicative-expression>)*
+<multiplicative-expression> ::= <primary-expression> (<ows> ('*' | '/') <ows> <primary-expression>)*
+<primary-expression>        ::= <integer>
+                              | <identifier>
+                              | '(' <ows>  <expression> <ows> ')'
+
 <assign-expression>   ::= <variable-name> <ows> <assign-operator> <ows> <expression>
 <assign-operator>     ::= '='
                         | '*='

base-commit: 7cd840ea689751643d2dd022b81d12d9581800cb
-- 
2.44.0

[olang/patches/.build.yml] build success

[builds.sr.ht]

olang/patches/.build.yml: SUCCESS in 44s

[spec: ebnf: add binary expressions][0] from [Johnny Richard][1]

[0]: https://lists.sr.ht/~johnnyrichard/olang-devel/patches/51036
[1]: mailto:johnny@johnnyrichard.com

✓ #1196562 SUCCESS olang/patches/.build.yml https://builds.sr.ht/~johnnyrichard/job/1196562

Re: [PATCH olang v1] spec: ebnf: add binary expressions

[Carlos Maniero]

>  (* Expressions *)
> -<expression>          ::= <integer> | <identifier>
> +<expression>                ::= <binary-expression>
> +<binary-expression>         ::= <logical-or-expression>
> +<logical-or-expression>     ::= <logical-and-expression> (<ows> '||' <ows> <logical-and-expression>)*
> +<logical-and-expression>    ::= <bitwise-or-expression> (<ows> '&&' <ows> <bitwise-or-expression>)*
> +<bitwise-or-expression>     ::= <bitwise-xor-expression> (<ows> '|' <ows> <bitwise-xor-expression>)*
> +<bitwise-xor-expression>    ::= <bitwise-and-expression> (<ows> '^' <ows> <bitwise-and-expression>)*
> +<bitwise-and-expression>    ::= <cmp-eq-and-neq-expression> (<ows> '&' <ows> <cmp-eq-and-neq-expression>)*
> +<cmp-eq-and-neq-expression> ::= <cmp-lt-and-gt-expression> (<ows> ('==' | '!=') <ows> <cmp-lt-and-gt-expression>)*
> +<cmp-lt-and-gt-expression>  ::= <bitwise-shift-expression> (<ows> ('<' | '>') <ows> <bitwise-shift-expression>)*
> +<bitwise-shift-expression>  ::= <additive-expression> (<ows> ('<<' | '>>') <ows> <additive-expression>)*
> +<additive-expression>       ::= <multiplicative-expression> (<ows> ('+' | '-') <ows> <multiplicative-expression>)*
> +<multiplicative-expression> ::= <primary-expression> (<ows> ('*' | '/') <ows> <primary-expression>)*
> +<primary-expression>        ::= <integer>
> +                              | <identifier>
> +                              | '(' <ows>  <expression> <ows> ')'

I'd like to get your opinion: Is it really necessary to represent
precedence here? Some language specifications [1] chose to omit this
detail. I' more inclined to keep the spec as simple as possible, even if
it makes the behavior a bit unclear. I believe it's more important to
represent our grammar in the spec rather than precisely detail how
olang behaves. Alternatively, we could follow Go's approach; they kept
the spec simple and added explanatory text about the language's
behavior.

But again, I just wanna an opinion here, I'm totally OK following the
spec you wrote, because I know that I suck at understanding the
precedence climbing method. :-)


[1]: Golang EBNF: https://go.dev/ref/spec#Expression / Rust EBNF:
https://web.mit.edu/rust-lang_v1.25/arch/amd64_ubuntu1404/share/doc/rust/html/grammar.html#binary-operator-expressions

Re: [PATCH olang v1] spec: ebnf: add binary expressions

[Johnny Richard]

On Tue, Apr 16, 2024 at 12:33:58AM -0300, Carlos Maniero wrote:
> I'd like to get your opinion: Is it really necessary to represent
> precedence here? Some language specifications [1] chose to omit this
> detail. I' more inclined to keep the spec as simple as possible, even if
> it makes the behavior a bit unclear. I believe it's more important to
> represent our grammar in the spec rather than precisely detail how
> olang behaves. Alternatively, we could follow Go's approach; they kept
> the spec simple and added explanatory text about the language's
> behavior.
> 
> But again, I just wanna an opinion here, I'm totally OK following the
> spec you wrote, because I know that I suck at understanding the
> precedence climbing method. :-)
> 
> 
> [1]: Golang EBNF: https://go.dev/ref/spec#Expression / Rust EBNF:
> https://web.mit.edu/rust-lang_v1.25/arch/amd64_ubuntu1404/share/doc/rust/html/grammar.html#binary-operator-expressions

I think the language specification should address all gramma aspects of
the language syntax, and precedence is a very fundamental part of the
syntax.

Being clear about the precedence rules in our grammar will prove its
worth once we begin adding more features to our parser.

Changing subject, if you are happy with this change and want to
integrate it, I want to change the patch title to:

    docs: spec: add binary expressions

I will appreciate a lot if you could make this change when applying the
patch.

Thanks for your review. <3

Re: [PATCH olang v1] spec: ebnf: add binary expressions

[ricardo_kagawa]

- This patch is missing the `%` operator;
- This patch seems to be missing the `>=` and `<=` operators.

> I'd like to get your opinion: Is it really necessary to represent
> precedence here? Some language specifications [1] chose to omit this

My opinion is that there are trade-offs to consider before deciding for
either convention or anything in-between. I suspect these are the
trade-offs to consider:

1. Implement precedence as part of the parser or as part of semantic
analysis;
2. Document precedence as part of the grammar or as a comment about the
grammar.

For the first item, if precedence is represented in the grammar, it
might be possible to evaluate expressions in the correct order during
parsing. Otherwise, the grammar is still valid, but semantic analysis
must find the correct order of expressions after parsing. The grammar
may be made simpler, but the complexity does not really go away.

For the second item, if precedence is represented in the grammar, you
don't have to define it authoritatively somewhere else (you may have
other informational documents describing that same precedence), so it is
automatically up-to-date. Otherwise, the grammar can be made simpler,
but it must refer to somewhere else to clarify what the precedence is,
which has to be updated separately.

Since the grammar is not used to generate the parser, there is less
benefit to representing precedence in the grammar. Still, I'd prefer to
represent it in the grammar, since I'm already familiar with that
convention, which might be the case for many other people and perhaps
even tools.

What really matters is that you are able to convey your intentions in
regards to language design, so that everyone from devs to users have a
close enough understanding to properly implement, use and reason about
it. Whatever you feel is clear enough for most people should be good
enough.

Re: [PATCH olang v1] spec: ebnf: add binary expressions

[Johnny Richard]

On Tue, Apr 16, 2024 at 08:17:15PM -0300, ricardo_kagawa@disroot.org wrote:
> - This patch is missing the `%` operator;
> - This patch seems to be missing the `>=` and `<=` operators.

Thanks for reporting this, I have sent a new patch to add the missing
operators.

patch-id: 511094b0e43e142504b4d3db8d8d72ff2d853e51

Re: [PATCH olang v1] spec: ebnf: add binary expressions

[Johnny Richard]

This patch has been superseded by v2:

Message-ID: <20240416233722.9441-1-johnny@johnnyrichard.com>