here is the link: http://caribchess.net/index.php?opt...,

You are in luck and I do have some good news for you. Try using PARAM instead of SPAN and you will be back in business. Note: PARAM doesn’t use a closing tag.

Would it be possible for the Chessviewer to represent moves of a pgn file textually, with fen lines? Such lines could be stored in the database and would allow fen position searches.

I'm really glad that CG took care of this problem with a magnanimous solution -

<<Viewer Deluxe> We are very sorry about that; you've now been granted an honorary lifetime membership.>

Hehehe... Well, of course you don't! ;) I'm just glad that you can go on from here unhindered by minor details such as, <"When does my <CG.com> Premium membership expire? I seem to have misplaced it..."> Keep up the good work! :^) - Mal

Feel free to elaborate on my forum. Or here, whichever you prefer.

<a joke that isn't funny won't get any funnier by appending a few smiley faces>

What really matters is that the person to whom the joke was directed had no problems with it.

BTW, visiting here has reminded me that I still owe you snapshots of Shredder having no problem with that PGN that had illegal third castling in it. Sorry about the delay - the entire thing skipped my mind.

Here they are:

http://docs.google.com/View?docid=d...

Returning to the exchange we had half a year ago: <Viewer Deluxe: <MostlyAverageJoe>, Of course, CVD is an enforcer. It implements and closely follows the PGN standard. As we all know having a portable notation turned out to be very important for chess.>

Given how the PGN "standard" came to be (by widespread adaptation, rather than by a well organized standardization process like the real standards, for example those here: http://www.open-std.org/), I would not treat it as a bible. It is hard to respect a "standard" that defines a format of a document without providing BNF of the grammar, especially if that format is as simple as PGN.

<Claiming PGN compatibility is taken very seriously in CVD. Another enforcing aspect is to allow only legal moves to be made by the user (drag-and-drop feature).>

I have no problems with the enforcement of the moves being entered by the user. But I do object to being unable to replay the game that actually happened.

Yes, if a move is physically impossible, then it should be treated as an error. An illegal move that could be otherwise made (and, if not called by the players as illegal it would STAND in rapid/blitz play), should be possible to replay. A warning is what is called for in such situation, not an error.

You seem to equate compatibility with a refusal to handle easily correctible mistakes.

The old viewer did it correctly, and in this respect CVD is a step backward.

Better late then never! Thanks for sharing your ideas. Here are few of my thoughts:

I do feel strongly about PGN although I don’t use religious terms for it. The importance of PGN is widely NOT understood and I try to excuse non-technical people. I’m sure it’s easier for you to appreciate it. Just imagine what would we have had if there wasn’t such a standard. Certain companies would have been selling us their proprietary databases with no alternatives. Then, what if they pull the plug? I'm not bothered about how well the process of developing the standard should’ve been organized. In the end, any standard is better than no standard and that’s one reason PGN is so successful. One unforeseen problem with PGN is that it creates a false sense of familiarity and non-technical chess players only “think” that they know about it. Yes, there is also a bright side of that but software developers have no excuse for just scratching the surface.

Of course, PGN has its BNF. Didn’t I mention it before? It’s in the specification. What you call simple above is, in fact, the PGN’s grammar. Its semantics is of magnitude harder. For example, if a Java parser gets to “n = k + 37;” it knows exactly what it means anywhere is the text and doesn’t even care about the semantics. Is the assignment legal? Back in PGN if you have “Bxf7+” it may or may not be legal for a long list of reasons. It may even be legal but not a check. When you consider it all you start realizing that parsing a PGN stream implies complete understanding of all chess rules. That’s why we have to have the rules fixed and strictly followed.

The second point you made is what I refer to as “almost legal” moves. You’re right that such moves exist and should be allowed. Again, PGN clearly defines them. Good example is a “Bxf7+” which isn’t an actual check but legal otherwise. Such move is allowed in the “import” format. There are few other features that allow relaxed syntax but anything else is called illegal with no adjectives.

<“What about exceptions that broke the rules but actually happened?”> you ask. I already answered that. The standard provides a powerful way of expressing any of those – a separate “half-game” needs to be created that starts from the where the first “half” ends. Nobody said that a single game should only contain one tags+movetext sections.

Well, I'l be darned, so it has: <18: Formal syntax>. My bad.

Of course, a less sloppily written document would place it in a more logical position than AFTER <16: Additional chess data standards> which is where I stopped reading. Or perhaps it would mention the presence of BNF somewhere prominently. For example, the nearly 800-pages 2001 IEEE Standard for Verilog Language tells you right at the beginning where to find the BNF.

Also, the BNF in section 18 is woefully incomplete, as it fails to define many of the terms used therein, forcing you to chase through the textual description which sometimes may be open to misinterpretation.

One of the effects of this sloppiness is that the syntax definition, as it is presented in the document, contradicts the premises used to define it. Or you get internal inconsistencies. Or both, as the example below shows.

Consider the stated goal that the import format should allow for manually prepared data. One of the most common mistakes in manually typed data is concatenation of two words together. If a disambiguation of a such concatenation is possible, user-friendly software should do it without barfing.

Take this game, for example: S Bernstein vs M L Hanauer, 1938. In that game, CDV complains about this portion:

< 32.Rd7+Kxd7 >

Consider this excerpt from the formal syntax:

<
<element-sequence> ::= <element> <element-sequence>

          <recursive-variation> <element-sequence>

          <empty>

<element> ::= <move-number-indication>

          <SAN-move>

          <numeric-annotation-glyph>

>

If you look at the textual description of the SAN, then, unless I misread something, the SAN-move *MUST* terminate at the + sign, since this sign is always a suffix. Therefore, the text <32.Rd7+Kxd7> should be properly parsed thus:

<move-number-indication> <period> <SAN-move> <SAN-move>

and any code that fails to parse that text in that exact manner is in violation of the formal syntax section.

On the other hand, the PGN description also allows interpretation of the entire sequence <Rd7+Kxd7> as a single symbol.

So, there you have: a sloppy, ambiguous, contradictory description, aided by a buggy distributed parser (with hand-written lexer and parser, as if flex & bison were not available since the late 1980s), both of the above showing serious confusion between what is syntax and what is semantics. Net result: a failure to parse an unambiguous, expectable mistake in the human input.

The acceptance of illegal moves should be just another facet of truly user-friendly implementation. Yes, it should produce a warning. But there is no reason to refuse it to play, other than the badly thought-up and impossible to contest/correct (since the coordinator apparently cannot be reached) restriction <Because illegal moves are not real chess moves, they are not permitted in PGN movetext. They may appear in commentary, however. One would hope that illegal moves are relatively rare in games worthy of recording>.

Your wish for a user friendly parser that can understand <32.Rd7+Kxd7> is not realistic. Lack of delimiter isn’t tolerated in any formal language but I’m willing to try it anyway.

1) The check indicator “+” has no meaning because it could be wrong. Think of it as optional so it can’t serve as a delimiter. Even worse, PGN specs explain why we can’t use “+” to disambiguate moves. For example, “Ne5+” is illegal even if there is only one knight move that results in check. Many people would react “why not” or “that’d be cool”;

2) Capture indicator “x” has a similar status. It is mandatory on capture moves but if used on other moves doesn’t invalidate them;

3) If we modify our move to read <32.Rd7Kd7> it becomes obvious why it cannot be separated. It could perfectly be a move in LAN;

4) Semantics is irrelevant during syntax analyses and so is objection like “but moving from d7 to d7 doesn’t make sense”. Moves don’t have to make sense or be legal. In my own interpretation of PGN illegal moves exist not only in comments as the original PGN specs “hope”.

Let’s take this move <32.Qe5?e6>. It could easily be two moves “32.Qe5? e6” or one move “32.Qe5e6”. Again, we cannot use semantics like “we don’t have a queen on e5 so it must be two moves then.” Only after we have the single move token (ie Qe5) we can start semantic analyses on it (ie which of our queens, if any, can move to e5).

One more example, <Ne4e5>. We know a knight can’t move from e4 to e5 hence we should split this into two moves. Those types of analyses will unnecessary increase the complexity. For example, if we implement them we won’t be able to easily enter “e3e4” as a LAN move (isn’t it two moves?). Unless we further increase the complexity by analyzing the pawn structure. No, thanks. The PGN specs draw a line at what is reasonable and worth implementing.

On the other hand, PGN does allow implied delimiters. For example, start/end of comment “{}” and start/end of variation “()” can be used without an explicit delimiter. The sad story is that users avoid doing it because so many buggy parsers can’t handle it. Another less known PGN fact is that move numbers are optional. Users shouldn’t waste time numbering the moves – PGN compliant software will do it for us.

And, finally, here is your treat.
A quick look at the BNF will be enough for you to see that empty variations are allowed. So, what? Here is a wish of mine that came true because of this little feature. You’re now able to include the following new (empty) variation when you analyze a game.

<...>({After some preparation a sacrifice on f7 might work.}) <...> Such a comment is clearly part of a new variation and doesn’t belong anywhere else in the text. It will invite you back in the future and (using CVD) you will be able to append the new moves into the empty variation. Of course, the comment will be preserved as part of the variation.

To call itself PGN compliant CVD allows and preserves even completely empty variations like “()”.

How many PGN parsers do you know that support this feature?

Enjoy!

Here is the position:

click for larger view

Two separate moves almost work except for a small detail.

<Which knight do we move first?>

Oh, yeah, I got it :-)
If we moved the d2 knight then g1=Q+ won’t be a check so it must be the knight on e1 we should move first. The perfect (imaginary) parser should produce: "Ne1-f3 g2-g1=Q+"

I hope you can see how clumsy and unrealistic such approach would be. Our next step would be to implement backtracking the way regular expressions do it. It isn’t impossible but you will start worrying about parsing speed pretty soon. That’s why we agree on a common ground (PGN) that’s good for most people.

Hey, <Viewer Deluxe>, I am a bit curious now: did you adopt & improve the parser from the SAN kit that is available in a couple places on the web, or did you write your own? Even the ancient lex/yacc would make it possible to easily parse things like the one above, so I am really surprised with your claim.

<Lack of delimiter isn’t tolerated in any formal language>

Unless I am mistaken, a legal move cannot have anything past the '+' sign, so upon encountering it, the lexer can safely return the token read so far. If the '+' is omitted, then we have a bit different story, but it is still possible to parse the text; see below.

<I hope you can see how clumsy and unrealistic such approach would be.>

On the contrary, it is quite simple to do a better parsing job, even without getting into the full scope of GLR parsing.

The following pseudo code outline would work for missing delimiters, using the usual greedy 'longest match' approach, except not with regular expressions. It is based on preserving the legality of the position (a good assumption, since it is true at the beginning of the game).

I bet this is quite similar to what you're already doing, except you grab the entire "symbol" as defined in the PGN document and test the legality then, instead of testing after every character.

<

while (next character cannot start a move)

    handle move numbers, variation, etc., etc.

token = ""

while (token is not a legal move in the current position)

    append the next character to the token;

// Now you have a legal move. See if it can be extended by appending more characters and remain legal.

while (token is a legal move in the current position)

    append the next character to the token;

drop the last character from the token

push back that character to the input stream

if (not EOF)

    apply the move to the position

    go back to the beginning

>

You apparently underestimated my “Nf3g1=Q+” example above. Keep in mind that there might be any number of intermediate moves between Nef3 and g1=Q+. Going back like that after every new move (while the current position might not be valid) is something that reminds me of backtracking but in more complex environment.

Your ideas for PGN parsing are quite different from what I do in my parser. If you ever implement them I’d like to see the performance testing results. In my experience some areas would need improvement:

1) I already explained that mixing syntax and semantics is to be avoided as much as possible. You are going one big step backwards. Your mixture of lexical, syntax and semantics analyses is facing a lot of problems;

2) Such enormous number of redundant checks for legal moves will definitely affect the efficiency. Punishing the “good citizens” (who don’t mind using white space where needed) by making them wait cannot be justified by the goals you defined;

3) The essence of your algorithm is saying “any illegal move WILL become legal by mere appending new characters to it”. That in your own words is “hopeful” thinking. In practice, the very first illegal move will cause the whole input stream to be used up;

4) You need to define your lexemes – moves being the most important one. For example, take my “Nf3g1=Q+” and let’s imagine you’re in the middle and your current token is “Nf3g”. Is this move legal? How can you check it? The correct answer is: “That’s not a move at all and you cannot check it”. You might introduce a new term like “incomplete move” but sooner or later you will have to define your lexemes based on syntax and not on semantics. Why were you asking about BNF at all? You seem to cope without it.

To sum up, IMHO, being able to do something doesn’t automatically justify doing it. Bill Clinton is popular prove for that.

<I’m yet to see other PGN parsers that support empty variations and multiple comments the way PGN specs defined them> Strange, since both of these are very easy to do.

Regarding your point (1): pardon me, but you first started mixing syntax and semantics in the discussion of <32.Rd7+Kxd7>. Whether or not the '+' is semantically valid has nothing to do with the fact that syntactically a + followed by a K terminates the half-move right where the <+> ends and <K> begins.

Your point (2) might have been valid in the early 1990s, but not nowadays. Parsing and verifying a page of text is trivial. A quick scripted hack in Tcl that I used to parse the entire CG collection of PGNs handled their 500,000+ games in about 10 minutes (and I wrote that "parser" while downloading the zipfiles, in about half an hour total - an easy tastk because I did not care about the comments and variations and just wanted to be able to strip them off). If I bothered to use flex & bison, it would be at least an order of magnitude faster, but it was good enough for the task at hand and I did not feel like spending time on writing a real parser for PGN. Since my highly inefficient implementation can parse a game in about a millisecond, I am not particularly scared of the performance implications of look-ahead validation.

Incidentally, my hack parses <Rd7+Kxd7> correctly as two half moves, without requiring any separators (although the version I had after 29 minutes did not - this is how I found S Bernstein vs M L Hanauer, 1938 and was surprised that <CDV> also did not parse that game).

Your point (3) does not represent what I said. Nowhere close.

Regarding your point (4) <You need to define your lexemes> -- that's what I've been trying to hint at, without creating unnecessary innuendos. It is trivial to write regular expressions that will match context-free valid moves. You don't have to use definition of a "symbol" in the PGN description to recognize your tokens, particularly since it that (overly generic) definition is inconsistent with SAN and LAN.

First, I already used more subtle ways of suggesting that every developer should start by reading the entire PGN specification. To put it straight, the single goal of Mr. Joe’s above is eliminating the need of white spaces as a delimiter. Unfortunately, that goal has nothing to do with PGN as we can see in the second paragraph of “Ch 1: Introduction”:

“PGN is structured for easy reading and writing by human users…” <Isn’t this crystal clear?>

Wehavetousespacesforourownsakebecauseeveryhumanw-
illhavetroublesunderstandingtextwithoutspaces.It-
doesn’tmatterifcomputerscoulddowithoutit.

If our goal was to compress the input stream we would’ve done much better than eliminating spaces and there wouldn’t have been any need for parsing. That is the approach already used in several proprietary binary formats. Therefore, once again, read the PGN specification as many time as you can before trying to improve it.

Second, these (current) pages are dedicated to a Web based chess viewer (CVD) that runs inside users’ browsers. The process involves downloading the CVD’s code to the client’s computer and getting the PGN data from the server. I’m sorry to have to state the obvious but any performance numbers from standalone environments are completely irrelevant. Comparing apples and oranges doesn’t work. Long explanations aren’t going to help either. Missing a point like that is known as “missing the boat”.