what type of grammar GO programming language?

[P. J.]

Hello,

My name is Péricles and I'm Brazilian and student of computer science
in my city.

I don't know if this list is appropriate place for to do this kind of
question, but i need off a help for determine what type of grammar of
the GO Programming language, if it is of type LL (1)? I looked the
documentation off the grammar in language site, but I confess, I
didn't understand very well.

I would like someone knows the subject and speaks certainty about this
or recommend a good link with this information.

Please excuse me my english and thank you by your attention

--
| .''`. A fé não dá respostas. Só impede perguntas.
| : :' :
| `. `'`
| `- P.J. - http://wiki.dcc.ufba.br/~PeeJay

[Ian Lance Taylor]

"P. J." <pjot...@gmail.com> writes:

> My name is Péricles and I'm Brazilian and student of computer science
> in my city.
>
> I don't know if this list is appropriate place for to do this kind of
> question, but i need off a help for determine what type of grammar of
> the GO Programming language, if it is of type LL (1)? I looked the
> documentation off the grammar in language site, but I confess, I
> didn't understand very well.
>
> I would like someone knows the subject and speaks certainty about this
> or recommend a good link with this information.

The Go grammar is LALR(1). You can see it in src/cmd/gc/go.y. It's
nearly LL(1), but I think it fails to be LL(1) (or even LL(k)) when
parsing a function signature, because it requires arbitrary lookahead to
distinguish
f(a, b, c, d)
f(a, b, c, d int)

This is no problem for an LALR(1) parser, but I think it is a problem
for an LL(1) parser. Or I could easily have completely misremembered
how this stuff works in which case I'm sure somebody will correct me.

A more interesting feature of the Go grammar is that it can be parsed
without a symbol table.

Ian

[⚛]

On Oct 18, 3:43 am, "P. J." <pjotam...@gmail.com> wrote:
> Hello,
>
> My name is Péricles and I'm Brazilian and student of computer science
> in my city.
>
> I don't know if this list is appropriate  place for to do this kind of
> question, but i need off a help for determine what type of grammar of
> the GO Programming language, if it is of type LL (1)? I looked the
> documentation off the grammar in language site, but I confess, I
> didn't understand very well.

The language specification (golang.org/doc/go_spec.html) is not LL(1)
or anything like that. In particular, you don't know whether an
expression like X(Y) is a type conversion or a function call until you
parse the whole Go package (a package is one or more .go files) and
perform symbol resolution. As Ian noted, expressions can be parsed
without a symbol table - but at the cost of *not* distinguishing
between function calls and type conversions in the parser (see Bison
file "src/cmd/gc/go.y" in Go implementation). Similarly, Go function
signatures can be parsed with LL(1) or something - at the cost of not
distinguishing between parameter names and parameter types in the
parser.

Go files can be parsed with any kind of computer science concept
(LL(1), LALR, etc) you choose - the only question is what the parser
did *not* recognize/distinguish. The unrecognized parts are processed
in later stages of compilation.

[chris dollin]

On 18 October 2011 09:22, ⚛ <0xe2.0x...@gmail.com> wrote:

> The language specification (golang.org/doc/go_spec.html) is not LL(1)
> or anything like that. In particular, you don't know whether an
> expression like X(Y) is a type conversion or a function call until you
> parse the whole Go package (a package is one or more .go files) and
> perform symbol resolution. As Ian noted, expressions can be parsed
> without a symbol table - but at the cost of *not* distinguishing
> between function calls and type conversions in the parser (see Bison
> file "src/cmd/gc/go.y" in Go implementation).

Well, that's true, but that's more of an antiproblem than a problem.
I wouldn't call it a "cost", more a simplification.

Chris

--
Chris "allusive" Dollin

[Russ Cox]

On Tue, Oct 18, 2011 at 00:07, Ian Lance Taylor <ia...@google.com> wrote:
> The Go grammar is LALR(1).  You can see it in src/cmd/gc/go.y.  It's
> nearly LL(1), but I think it fails to be LL(1) (or even LL(k)) when
> parsing a function signature, because it requires arbitrary lookahead to
> distinguish
>        f(a, b, c, d)
>        f(a, b, c, d int)
>
> This is no problem for an LALR(1) parser, but I think it is a problem
> for an LL(1) parser.  Or I could easily have completely misremembered
> how this stuff works in which case I'm sure somebody will correct me.

If you approach it that way, then it needs unlimited lookahead,
even in an LALR(1) grammar, because you don't know until you
have parsed an arbitrary amount of extra stuff how to reduce the 'a'.

However, you can parse the function parameter list as a comma-separated
list of either (a) name, (b) type, or (c) name and type, and then apply
the semantic meaning later. (a) and (b) can be treated as the same case,
so it's a comma-separated list of [name] type, at least as far as the
grammar is concerned.

Russ

[Ian Lance Taylor]

Russ Cox <r...@golang.org> writes:

> If you approach it that way, then it needs unlimited lookahead,
> even in an LALR(1) grammar, because you don't know until you
> have parsed an arbitrary amount of extra stuff how to reduce the 'a'.

Yeah, but LALR(1) grammars have a form of unlimited lookahead because
they get to use a pushdown stack, unlike LL(1) grammars. Or at least
that is my vague recollection of this stuff.

Ian

[Dave Dolan]

Ian is mostly right. In LALR(1) Each rule can only match with one
token of lookahead, but you can construct productions where the rules
consist solely of other non-terminals to 'simulate' as much lookahead
as you need.  The terminology doesn't exactly match, but the idea is
like that.

[P. J.]

Hello personal,

2011/10/18 Ian Lance Taylor <ia...@google.com>:

Thank you very much by the help of you (Ian and Russ).

Excuse for the delay in answer.

[ ] 's

Péricles

[⚛]

On Oct 19, 3:32 pm, "P. J." <pjotam...@gmail.com> wrote:
> Hello personal,
>

> 2011/10/18 Ian Lance Taylor <i...@google.com>:

>
> > Russ Cox <r...@golang.org> writes:
>
> >> If you approach it that way, then it needs unlimited lookahead,
> >> even in an LALR(1) grammar, because you don't know until you
> >> have parsed an arbitrary amount of extra stuff how to reduce the 'a'.
>
> > Yeah, but LALR(1) grammars have a form of unlimited lookahead because
> > they get to use a pushdown stack, unlike LL(1) grammars.  Or at least
> > that is my vague recollection of this stuff.
>
> Thank you very much by the help of you (Ian and Russ).

... now you will have to explain what I did wrong, so that I can
prevent it from happening again.

[⚛]

On Oct 18, 6:07 am, Ian Lance Taylor <i...@google.com> wrote:
> The Go grammar is LALR(1).  You can see it in src/cmd/gc/go.y.  It's
> nearly LL(1), but I think it fails to be LL(1) (or even LL(k)) when
> parsing a function signature, because it requires arbitrary lookahead to
> distinguish
>         f(a, b, c, d)
>         f(a, b, c, d int)

Maybe the question I would like to raise has already discussed in
golang-nuts (a quick search didn't found a prior discussion), but
wouldn't it be better to separate parameter names belonging to the
same type by a space instead of using a comma?

For example:

func f(a b c int)
func f(a b c int) (x y string, z os.Error)

[Steven Blenkinsop]

Or like a var declaration/struct type literal:
func f(a, b int; c byte)(x, y string; z os.Error)

Or bracketed lists:
func f((a, b) int, c byte)((x, y) string, z os.Error)

Or use a keyword:
func f(a diddly b int, c byte)(x diddly y string, z os.Error)

Or...

Depends on your definition of better. Playing with the punctuation sort of makes it less clear that you're defining the name/type bindings of a comma separated list. Though, on the other hand, structs already do this, since composite literals are also comma separated, so it might not be so bad. It would be odd, since nowhere else in the language can variable identifiers sit next to each-other. It would also raise the question about comma separated lists in multiple assignment.

[Ian Lance Taylor]

On Wed, Oct 19, 2011 at 9:29 AM, ⚛ <0xe2.0x...@gmail.com> wrote:
>
> Maybe the question I would like to raise has already discussed in
> golang-nuts (a quick search didn't found a prior discussion), but
> wouldn't it be better to separate parameter names belonging to the
> same type by a space instead of using a comma?
>
> For example:
>
>  func f(a b c int)
>  func f(a b c int) (x y string, z os.Error)

What is the advantage of doing that?

The current grammar is unambiguous, and the syntax is the same as for
a var declaration.

Ian

[⚛]

On Oct 19, 7:27 pm, Ian Lance Taylor <i...@google.com> wrote:

> On Wed, Oct 19, 2011 at 9:29 AM, ⚛ <0xe2.0x9a.0...@gmail.com> wrote:
>
> > Maybe the question I would like to raise has already discussed in
> > golang-nuts (a quick search didn't found a prior discussion), but
> > wouldn't it be better to separate parameter names belonging to the
> > same type by a space instead of using a comma?
>
> > For example:
>
> >  func f(a b c int)
> >  func f(a b c int) (x y string, z os.Error)
>
> What is the advantage of doing that?

Those commas are redundant.

It has no effect on readability of function signatures (in my view).

> The current grammar is unambiguous,

The modified grammar is also unambiguous.

> and the syntax is the same as for
> a var declaration.

In a var declaration, commas on the LHS are intuitive because the RHS
requires commas to separate expressions. Parameters in a function
signature have no RHS.

[Jan Mercl]

On Wednesday, October 19, 2011 7:55:38 PM UTC+2, ⚛ wrote:

Those commas are redundant.

I don't think so. See: http://code.google.com/p/go/source/browse/src/cmd/gc/go.y#1445 and bellow.

 

The modified grammar is also unambiguous. 

AFAICS, yacc would disagree.

[⚛]

On Oct 19, 8:09 pm, Jan Mercl <jan.me...@nic.cz> wrote:
> On Wednesday, October 19, 2011 7:55:38 PM UTC+2, ⚛ wrote:
>
> > Those commas are redundant.
>

> I don't think so. See:http://code.google.com/p/go/source/browse/src/cmd/gc/go.y#1445and bellow.

>
> > The modified grammar is also unambiguous.
>
> AFAICS, yacc would disagree.

I do not understand what you mean (in either of the two cases you
mentioned).

[Kyle Lemons]

func(a, b, int, a string)

func(a b int a string)

The first one is unambiguous, the second could be considered unambiguous but would change the semantics.

~K

[Kyle Lemons]

func(a, b, int, a string)

func(a b int a string)

er, make the second "a" in both cases a "c"

[Paul Borman]

I think it is worth pointing out the following (with all its implications) is legal:

var int int

But the following is not

var int int

var i int

I don't recommend it, but it is worth remembering.

    -Paul

[Andrew Hart]

On Oct 19, 5:15 pm, Paul Borman <bor...@google.com> wrote:
> I think it is worth pointing out the following (with all its implications)
> is legal:
>
> var int int
>
> But the following is not
>
> var int int
> var i int
>
> I don't recommend it, but it is worth remembering.
>
>     -Paul

That surprises me. I would expect
var int int
to parse as a VarDecl with an IdentifierList of "int" and a Type of
"int".
Likewise, I'd expect
var i int
to parse as a VarDecl with an IdentifierList of "i" and a Type of
"int".

Either line in isolation is fine. Also, swapping them is fine.

http://golang.org/doc/play/#package%20main%0A%0Afunc%20main()%20%7B%0A%20%20var%20int%20int%0A%20%20var%20i%20int%20%2F%2F%20swapping%20these%20lines%20makes%20the%20error%20go%20away%0A%20%20_%2C%20_%20%3D%20i%2C%20int%0A%7D%0A

Is this a bug? If not, what's going on?

-Andrew

[Jan Mercl]

On Thursday, October 20, 2011 7:17:04 AM UTC+2, Andrew Hart wrote:

Is this a bug? If not, what's going on?

Inside a func (the var and all) declarations are well ordered, outside a func they are not. That's the cause..

[Paul Borman]

From the spec:

Identifiers name program entities such as variables and types. An identifier is a sequence of one or more letters and digits. The first character in an identifier must be a letter.

int and nil are just predefined identifiers in the global scope (universal block) so you cannot redefine them there (they are already defined) but inside a new scope you are free to do so.  Just as you can shadow variables from an outer scope you can shadow types, to.

    nil := 1 // perfectly valid but misleading

    type string int // string is the new int

    var x string

    x = 1

Obviously you can abuse this, but it also means that code that is using a variable or type named "rune" (outside of the global scope) will still work after "rune" is introduced as a new type.

It actually is very beautiful.

    -Paul

[Andrew Hart]

Also playing into the example of "var int int" is an identifier of one
type can shadow an identifier of a different type. I now see that this
is described in the spec in the section "Declarations and scope".

It seems that prevents ambiguity elsewhere, such as in conversions
which might otherwise look like function calls.

-Andrew

[Tom (NiftyHat) Mitchell]

On Tue, Oct 18, 2011 at 1:22 AM, ⚛ <0xe2.0x...@gmail.com> wrote:
> On Oct 18, 3:43 am, "P. J." <pjotam...@gmail.com> wrote:
>> My name is Péricles and I'm Brazilian and student of computer science
>> in my city

.....snip....
> The language specification (golang.org/doc/go_spec.html)
...snip...

in the parser (see Bison
> file "src/cmd/gc/go.y" in Go implementation).

One answer for a student is that the grammar/ parser is
controlled by a yacc (Bison) file. See "src/cmd/gc/go.y".
A student should dig into the tutorials and books on "yacc" and
the open source version "bison". This would be an early
stop in a compiler class -- with exercises in designing and
implementing small/medium/large languages and parsers.

http://www.gnu.org/software/bison/manual/bison.html

See also "lex" (yylex).

As always there is more to look at:
http://www.gnu.org/software/bison/manual/bison.html#Bibliography
and
http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools#Second_edition

--

        T  o  m     M  i  t  c  h  e  l  l

[⚛]

On Oct 22, 12:14 am, "Tom (NiftyHat) Mitchell" <nifty.mi...@gmail.com>
wrote:

> On Tue, Oct 18, 2011 at 1:22 AM, ⚛ <0xe2.0x9a.0...@gmail.com> wrote:
> > On Oct 18, 3:43 am, "P. J." <pjotam...@gmail.com> wrote:
> >> My name is Péricles and I'm Brazilian and student of computer science
> >> in my city
> .....snip....
> > The language specification (golang.org/doc/go_spec.html)
>
> ...snip...
>  in the parser (see Bison
>
> > file "src/cmd/gc/go.y" in Go implementation).
>
> One answer for a student is that the grammar/ parser  is
> controlled by a yacc (Bison) file.  See  "src/cmd/gc/go.y".
> A student should dig into the tutorials and books on "yacc" and
> the open source version "bison".  This would be an early
> stop in a compiler class -- with exercises in designing and
> implementing small/medium/large languages and parsers.

I do not understand what you are talking about.

>  http://www.gnu.org/software/bison/manual/bison.html
>
> See also "lex" (yylex).
>
> As always there is more to look at:
>  http://www.gnu.org/software/bison/manual/bison.html#Bibliography
> and

>  http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_T...

[⚛]

On Sat, Oct 22, 2011 at 8:05 PM, Tom (NiftyHat) Mitchell
<nifty...@gmail.com> wrote:

>
> On Sat, Oct 22, 2011 at 1:38 AM, ⚛ <0xe2.0x...@gmail.com> wrote:
> > On Oct 22, 12:14 am, "Tom (NiftyHat) Mitchell" <nifty.mi...@gmail.com>
> > wrote

> :.....

> >> ...snip...
> >>  in the parser (see Bison
> >>
> >> > file "src/cmd/gc/go.y" in Go implementation).
> >>
> >> One answer for a student

> .......
>
> And you remarked to me.

>
> > I do not understand what you are talking about.
>

> My take on the question from the original poster
> was this was a take-home quiz question.
>
> Knowing the answer is often not the goal in a class.
> Knowing how to discover the answer is.
>
> Sort of like:  Answer = 42
>
> Without knowing the question and without
> showing "your work" the answer is not
> a real answer.

If you take a look into the file "src/cmd/gc/go.y" and compare it to
the grammar in the Go specification, you may be able to see some
examples of the grammar in the specification *not* being parseable by
Yacc/Bison because the Bison grammar uses different grammar rules in
several places and postpones the recognition to a later stage of
compilation.

I believe what I wrote in my 1st post in this forum thread has some
real value. If you have actual arguments (other than "42") that render
my post invalid, I would like you to present them to me. If your
argument is "examining the file src/cmd/gc/go.y" is pointless in
relation to the OP, it is a wrong argument.

[shuang cui]

wonderful！