FAQ
Hello. I was reading slides of a talk given by Russ and have problem
understanding the following slide:

http://talks.golang.org/2014/research.slide#30

The slide states that "Go programs can be parsed without context (unlike C
and C++)". I am not sure what this sentence means. Can somebody explain?

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Dan Kortschak at Feb 22, 2014 at 8:31 am
    type knowledge may be required to disambiguate parsing of C and C++
    On 22/02/2014, at 6:50 PM, "⚛" wrote:

    The slide states that "Go programs can be parsed without context (unlike C and C++)". I am not sure what this sentence means. Can somebody explain?
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Jan Mercl at Feb 22, 2014 at 9:25 am

    On Sat, Feb 22, 2014 at 9:31 AM, Dan Kortschak wrote:
    type knowledge may be required to disambiguate parsing of C and C++
    In a certain sense this is true for Go as well.

             f(x)

    can be a call operation or conversion operation, depending on the
    knowledge of what f stands for.

    However, I guess that formally, the "can be parsed without context" is
    equal to saying that there exists an unambiguous (LR(1)) grammar for
    the given language. Regarding the above example, the ambiguity is only
    semantic (to be resolved later), not syntactic -> the AST can be built
    without knowing what f is.

    IMO good analysis here:
    http://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-c%E2%80%99s-grammar-revisited/

    -j

    PS: Chris has a particularly nice example of the C problem.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Feb 22, 2014 at 9:50 am
    Yes, a fairly loose sense.

    I was thinking of 't f(x);'.

    On 22/02/2014, at 7:55 PM, "Jan Mercl" wrote:

    In a certain sense this is true for Go as well.

    f(x)

    can be a call operation or conversion operation, depending on the
    knowledge of what f stands for.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Aram Hăvărneanu at Feb 22, 2014 at 10:06 am
    You've written a Go compiler, I'm sure you know what context-free
    language are, so I'm confused about your conundrum. Go is not
    context-free, I suspect no real language is. However, it's much less
    context-sensitive than most other languages. The extreme example is
    C++.

    --
    Aram Hăvărneanu

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • ⚛ at Feb 22, 2014 at 10:24 am

    On Saturday, February 22, 2014 11:05:19 AM UTC+1, Aram Hăvărneanu wrote:
    You've written a Go compiler,

    True. Tulgo is using a hand written lexer and parser. I have found over
    time that hand written lexers and parsers are easy to write and easier to
    extend than automatically generated ones.

    I'm sure you know what context-free
    language are,

    I wouldn't be so sure about that. I am looking at compilation solely as an
    optimization problem and information extraction problem. Whether a
    particular language is context-free seems irrelevant from this viewpoint.

    so I'm confused about your conundrum. Go is not
    context-free, I suspect no real language is. However, it's much less
    context-sensitive than most other languages.

    I agree that, maybe, Go is less context-sensitive that other languages. But
    on the other hand Go needs to see the whole file before it can resolve a
    package identifier, while in C/C++ identifiers are usually processed
    sequentially.

    The extreme example is
    C++.

    --
    Aram Hăvărneanu
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Benjamin Measures at Feb 22, 2014 at 3:46 pm

    On Saturday, 22 February 2014 09:24:54 UTC, Jan Mercl wrote:

    In a certain sense this is true for Go as well.

    f(x)

    can be a call operation or conversion operation, depending on the
    knowledge of what f stands for.
    Go has function types. So, for the above example, f is just a type (no
    knowledge needed).

    In fact, whatever the type, the parser names this a
    CallExpr: http://play.golang.org/p/Lr9VtYvxJX

    Context-free grammers keep things really simple.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Benjamin Measures at Feb 22, 2014 at 3:46 pm

    On Saturday, 22 February 2014 15:45:57 UTC, Benjamin Measures wrote:
    Context-free grammers keep things really simple.
    s/grammers/grammars/

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Jan Mercl at Feb 22, 2014 at 5:29 pm

    On Sat, Feb 22, 2014 at 4:45 PM, Benjamin Measures wrote:
    On Saturday, 22 February 2014 09:24:54 UTC, Jan Mercl wrote:

    In a certain sense this is true for Go as well.

    f(x)

    can be a call operation or conversion operation, depending on the
    knowledge of what f stands for.

    Go has function types. So, for the above example, f is just a type (no
    knowledge needed).
    No knowledge needed to parse, knowledge needed to decide semantics
    (call or conversion?). But that was stated before, so just repeating.
    In fact, whatever the type, the parser names this a CallExpr:
    http://play.golang.org/p/Lr9VtYvxJX

    Context-free grammers keep things really simple.
    Fun fact. Go syntax is actually not a CFG. It's actually an ambiguous
    grammar for which you cannot even write a yacc parser. I know the gc
    uses a yacc based parser - yet the previous claim still holds ;-)

    -j

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Russ Cox at Feb 22, 2014 at 8:38 pm

    On Sat, Feb 22, 2014 at 12:28 PM, Jan Mercl wrote:

    Fun fact. Go syntax is actually not a CFG. It's actually an ambiguous
    grammar for which you cannot even write a yacc parser. I know the gc
    uses a yacc based parser - yet the previous claim still holds ;-)
    Whether this is true depends on what you define the syntax to be. Someone
    brought up conversions and function calls, but in Go those *are* the same
    syntax, so there is no ambiguity at the syntactic level. (The spec
    distinguishes them, but that doesn't mean a parser must.) In contrast, the
    "X * Y" example given earlier for C really does have two irreconcilably
    different parses, and without type information you cannot tell which it is.

    If you think Go's grammar is ambiguous, I think you are making too many
    distinctions in the parser.

    Russ

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Jan Mercl at Feb 22, 2014 at 9:18 pm

    On Sat, Feb 22, 2014 at 9:38 PM, Russ Cox wrote:
    On Sat, Feb 22, 2014 at 12:28 PM, Jan Mercl wrote:

    Fun fact. Go syntax is actually not a CFG. It's actually an ambiguous
    grammar for which you cannot even write a yacc parser. I know the gc
    uses a yacc based parser - yet the previous claim still holds ;-)

    Whether this is true depends on what you define the syntax to be. Someone
    brought up conversions and function calls, but in Go those *are* the same
    syntax, so there is no ambiguity at the syntactic level. (The spec
    distinguishes them, but that doesn't mean a parser must.) In contrast, the
    "X * Y" example given earlier for C really does have two irreconcilably
    different parses, and without type information you cannot tell which it is.
    Yep, I agree and I explicitly agreed to all of the above earlier.
    If you think Go's grammar is ambiguous, I think you are making too many
    distinctions in the parser.
    Actually it's not about me thinking this or that; the fact that the
    grammar is ambiguous is right in the specs[0]:

    """"
    A parsing ambiguity arises when a composite literal using the TypeName
    form of the LiteralType appears between the keyword and the opening
    brace of the block of an "if", "for", or "switch" statement, because
    the braces surrounding the expressions in the literal are confused
    with those introducing the block of statements. To resolve the
    ambiguity in this rare case, the composite literal must appear within
    parentheses.
    """"

    In fact, the yacc based parser of gc parses a different language (the
    not ambiguous one). This language is only slightly different and is
    produced by small tokenizer hacks (lbrace vs '{', fixlbrace(),
    contextual '()' and '[]' pairs tracing/balancing deciding when to hand
    which token for the same { symbol to the parser, ...).

    This is in no way saying that anything is wrong with this! It's just
    that the Go grammar really _is_ ambiguous. In just one place and in a
    such a place where the "problem" can be solved easily. And in a way
    which, IMHO, benefits the programmer, who is _not_ limited in the same
    way formal grammar of most parser generators is.

    As stated before - it's a fun fact, not a complain. I actually
    appreciate this design detail. It trades better readability in the
    common case for only a little bit more complicated parser.

       [0]: http://golang.org/ref/spec#Composite_literals

    -j

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Kevin Gillette at Feb 22, 2014 at 11:08 pm
    Perhaps. The fact is that the compilers don't accept inputs in which that
    ambiguity occurs, and it is indeed possible to define a grammar that is
    unambiguous in that respect yet precisely adheres to what the compilers
    accept. Therefore, the ambiguity claim feels somewhat philosophical to me.
    On Saturday, February 22, 2014 2:17:44 PM UTC-7, Jan Mercl wrote:

    On Sat, Feb 22, 2014 at 9:38 PM, Russ Cox <r...@golang.org <javascript:>>
    wrote:
    On Sat, Feb 22, 2014 at 12:28 PM, Jan Mercl wrote:

    Fun fact. Go syntax is actually not a CFG. It's actually an ambiguous
    grammar for which you cannot even write a yacc parser. I know the gc
    uses a yacc based parser - yet the previous claim still holds ;-)

    Whether this is true depends on what you define the syntax to be. Someone
    brought up conversions and function calls, but in Go those *are* the same
    syntax, so there is no ambiguity at the syntactic level. (The spec
    distinguishes them, but that doesn't mean a parser must.) In contrast, the
    "X * Y" example given earlier for C really does have two irreconcilably
    different parses, and without type information you cannot tell which it
    is.

    Yep, I agree and I explicitly agreed to all of the above earlier.
    If you think Go's grammar is ambiguous, I think you are making too many
    distinctions in the parser.
    Actually it's not about me thinking this or that; the fact that the
    grammar is ambiguous is right in the specs[0]:

    """"
    A parsing ambiguity arises when a composite literal using the TypeName
    form of the LiteralType appears between the keyword and the opening
    brace of the block of an "if", "for", or "switch" statement, because
    the braces surrounding the expressions in the literal are confused
    with those introducing the block of statements. To resolve the
    ambiguity in this rare case, the composite literal must appear within
    parentheses.
    """"

    In fact, the yacc based parser of gc parses a different language (the
    not ambiguous one). This language is only slightly different and is
    produced by small tokenizer hacks (lbrace vs '{', fixlbrace(),
    contextual '()' and '[]' pairs tracing/balancing deciding when to hand
    which token for the same { symbol to the parser, ...).

    This is in no way saying that anything is wrong with this! It's just
    that the Go grammar really _is_ ambiguous. In just one place and in a
    such a place where the "problem" can be solved easily. And in a way
    which, IMHO, benefits the programmer, who is _not_ limited in the same
    way formal grammar of most parser generators is.

    As stated before - it's a fun fact, not a complain. I actually
    appreciate this design detail. It trades better readability in the
    common case for only a little bit more complicated parser.

    [0]: http://golang.org/ref/spec#Composite_literals

    -j
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • ⚛ at Feb 23, 2014 at 7:58 am

    On Saturday, February 22, 2014 9:38:45 PM UTC+1, Russ Cox wrote:
    On Sat, Feb 22, 2014 at 12:28 PM, Jan Mercl <0xj...@gmail.com<javascript:>
    wrote:
    Fun fact. Go syntax is actually not a CFG. It's actually an ambiguous
    grammar for which you cannot even write a yacc parser. I know the gc
    uses a yacc based parser - yet the previous claim still holds ;-)
    Whether this is true depends on what you define the syntax to be. Someone
    brought up conversions and function calls, but in Go those *are* the same
    syntax, so there is no ambiguity at the syntactic level. (The spec
    distinguishes them, but that doesn't mean a parser must.) In contrast, the
    "X * Y" example given earlier for C really does have two irreconcilably
    different parses, and without type information you cannot tell which it is.
    In my opinion, Go's f(x) and C's X*Y are the same but in C's case the
    ambiguity propagates in a slightly different way through the parse rules.

    I agree that it is more appropriate to say that Go's grammar is
    context-free than to say that C's grammar is context-free.

    If you think Go's grammar is ambiguous, I think you are making too many
    distinctions in the parser.

    Russ
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Chris dollin at Feb 22, 2014 at 9:18 am

    On 22 February 2014 08:20, ⚛ wrote:

    Hello. I was reading slides of a talk given by Russ and have problem
    understanding the following slide:

    http://talks.golang.org/2014/research.slide#30

    The slide states that "Go programs can be parsed without context (unlike C
    and C++)". I am not sure what this sentence means. Can somebody explain?
    ...; X * Y; ...

    Is that a declaration or an expression?

    Chris

    --
    Chris "allusive" Dollin

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedFeb 22, '14 at 8:20a
activeFeb 23, '14 at 7:58a
posts14
users8
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase