(Part 2) Top products from r/AskProgramming

OK, a few things:

It looks like you're trying to build a shift/reduce parser, which is a form of an LR parser, for your language. LR parsers try to reduce symbols into more abstract terms as soon as possible. To do this, an LR parser "remembers" all the possible reductions that it's pursuing, and as soon as it sees the input symbols that correspond to a specific reduction, it will perform that reduction. This is called "handle finding".

> If I am correct, my Automaton is a DFA?

When the parser is pursuing a reduction, it's looking for sequences of symbols that match the right-hand sides of the relevant (to our current parse state) productions in our grammar. Since the right-hand sides of all the productions in a grammar are simple sequences, all the handle finding work can be done by a DFA. Yes, the handle recognizer of your parser is a DFA. But keep in mind that it needs to be combined with other parts to make a full parser, and your actual grammar can't be recognized with just a DFA.

In particular, you've shown the ACTION table for a shift/reduce parser. It determines what to do when you encounter a symbol in the input stream. But a shift/reduce parser typically needs a second table as well - the GOTO table - that determines what to do after a reduction has taken place.

One other thing that's worth mentioning: you've expressed your ACTION table as a plain DFA transition table. That's not necessarily wrong, but it's not commonly done that way. Instead of reducing when you reach a certain state, it's common to instead attach an action - either 'shift' or 'reduce' ('accept') - to each transition itself. So in a shift/reduce parser, your table might look more like this:

| [ | ] | < | > | id | / | attr
----+-----+-----+-----+-----+------+-----+--------
0 | S1 | | S4 | | | |
1 | | | | | S2 | | R3 : Reduce Tag -> [ id ]
2 | | R3 | | | | | R7 : Reduce Tag -> < id ??? / >
4 | | | | | S5 | S10 | R9 : Reduce Tag -> < id ??? >
5 | | | | R9 | | S6 | S8 R12 : Reduce Tag -> < / id >
6 | | | | R7 | | |
8 | | | | R9 | | S6 | S8
10 | | | | | S11 | |
11 | | | | R12 | | |

Note that R7 and R9 aren't well-formed, since multiple sequences of input tokens might cause you to reach these actions. While it would be possible to construct a shift / reduce parser this way, it's not commonly done. Typically, the DFA to recognize handles is an acyclic graph, but your have a self-transition in state 8.

> What would be the best way of implementing this automaton in C++? Do I really have to make a huge array?

In general, yes, you need a big array (or, as suggested before, two big arrays). But you can use any space-saving technique you want. For example, since most entries in the ACTION table are invalid, one could represent that data with a sparse array data structure. Also, both The Dragon Book and Cooper and Torczon briefly cover parser-specific ways to compress those tables. For example, notice that rows 5 and 8 in your example have the same entries. Most real grammars have multiple instances of identical rows, so factoring out this commonality can save enough space that the extra complexity is worth it.

---

I'm a little surprised that you're building a parser like this by hand, though. Typically people do one of two things:

1. Build, by hand, a modified LL(1) recursive descent parser (or variant, like a packrat parser)
   
2. Build, using a tool like YACC or Bison, a LR(1) shift/reduce parser
   
   You're sort of doing a mix of the two, which means you have the downsides of both approaches. You need to track all the states and transitions by hand, instead of relying on tools to automate that process, yet you don't get the flexibility of a hand-coded recursive descent parser.
   
   If you're doing this for education's sake, then by all means proceed. I'd highly encourage you to pick up a book on parsing; I think Cooper and Torczon is a great source. But if you just want a parser that works, I'd definitely recommend using a tool or using a more direct approach, like recursive-descent.

I was linked here from /r/shittyprogramming which seems rather unfair, but what you say makes no sense to someone who has never heard of this type of research before.

What you are talking about (in a half-assed way) is called genetic programming.. Koza's book is definitive and mind-blowing. Genetic Programming is sometimes related to Artificial Life.

I have dabbled in it, but a good book to read on the matter is a new kind of science, by wolfram. He makes some arrogant claims and makes out he invented the field, but he does have some rather good theories. I agree with him that some sort of cellular automation with a genetic component is the best way to start off the process.

A fascinating anecdote from the book is how the rate of chaotic change to create a stable cellular automata system was stumbled on in Conway's Game of Life. A slight adjustment to the rules one way led to an almost static system. The other way led to the board being filled up. There is a level of "just right" that leads to what some people think of "life" in the game of life.

You are correct that you do not need a scaled version of the current universe to eventually achieve AI, as a simplified model with evolution will do. It's a massive book with some rather complicated ideas, but if you are truly interested it is worth pursuing.

If you are just superficially interested in the field, a great sci fi novel set about these ideas is called Permutation City. Another book, Artificial Life by Steven Levy is a great history of alife so far.

Welcome to the field!

Here's part of a passage that really explains the differences well. I hope it's as helpful for you as it was for me.

This is from Problem Solving and Program Design in C:

Section 2
The College experience: Computer Disciplines and Majors to Choose From

Computer Science

> Computer science as a discipline encompasses a wide range of topics from theoretical and algorithmic foundations to cutting-edge developments. The work computer scientists are trained to do can be arranged into three categories:

> Designing and implementing useful software
> Devising new ways to use computers
> * Developing effective ways to solve computing problems

>A computer science degree consists of courses that include computing theory, programming, and mathematics. These courses ultimately develop the logic and reasoning skills integral to becoming a computer scientist. The math sequence includes calculus I and II (and in many cases, calculus III) as well as discrete mathematics. Some students also study linear algebra and probability and statistics. A computer science degree offers a comprehensive foundation that permits graduates to understand and adapt to new technologies and new ideas. Computer science departments are often found at universities as part of the science, engineering, or mathematics divisions.

> Computer scientists take on challenging programming jobs, supervise other programmers, and advise other programmers on the best approaches to be taken. Computer science researchers are working with scientists from other fields to perform such tasks as using databases to create and organize new knowledge, making robots that will be practical and intelligent aides, and using computers to help decipher the secrets of human DNA. Their theoretical background allows them to determine the best performance possible for new technologies and their study of algorithms helps them to develop creative approaches to new (and old) problems.

Software Engineering

> Software engineering (SE) is the discipline of developing and maintaining large software systems. These systems must behave reliably and efficiently, be affordable, and satisfy all requirements defined for them. SE seeks to integrate the theory of computer science and mathematics with the practical engineering principles developed for physical objects.

> An SE degree program is closely related to the computer science degree
program, and they are usually offered within the same department. In fact, most computer science curricula require one or more software engineering courses. An SE degree can be considered a specialized degree within the confines of the field of computer science.

> SE students learn more about software reliability and maintenance of large systems and focus more on techniques for developing and maintaining software that is engineered to be correct from its inception. Most programs require SE students to participate in group projects for the development of software that will be used in earnest by others. Students assess customer needs, develop usable software, test the product thoroughly, and analyze its usefulness.
Professionals who hold a software engineering degree expect to be involved with the creation and maintenance of large software systems that may be used by many different organizations. Their focus will be on the design principles that make the system viable for many people and through many years.

> Although an SE degree has a recognized description, the term software engineer is merely a job label in the workplace. There is no standard definition for this term when used in a job description, and its meaning can vary widely among employers. An employer may think of a programmer or an IT specialist as a software engineer.

These are great suggestions. The three books I typically give devs early (that fit in well with the two presented here) are:

Refactoring by Martin Fowler

This is a list of patterns of common refactoring a and how to do them safely. It’ll help you recognize transforms you need to make in your code as it changes.

The Pragmatic Programmer by Dave Thomas and Andy Hunt

This is a great guidebook for how to get better at being a software engineer. Essential read.

And while there are lots of options for design patterns books...

Head First Design Patterns was the one that helped me internalize them. Even if you aren’t writing much (or any) Java, the method of teaching is hugely valuable.

The requirements side is generally face to face coupled with passing a Word document back in forth. Everybody signs off before we begin.

I use paper and pencil, a white board, and my cat for the actual design work. Long walks, sleeping, discussing with colleagues and cat, and the occasional beer all help. You just have to give it some time to gel in your head and on paper. This can take anywhere from a few hours to several months.

For the really big projects we will walk through all of the business scenarios as a group to verify we have covered everything. If you don't know how something will be dealt with you're not finished.

You might find The Practice of Programming a useful read. Fair warning, it isn't web-centered at all, but still loads of good information.

I'm not much in to design tools, but would use if I was convinced they would help. I've seen them used and generally most of the time spent is goofing with the tool. They also tend to put unnecessary constraints on the solution.

I'd recommend learning the principles of programming first. Later you can apply those principles to app development, web dev, game dev, whatever. I would highly recommend How to Design Programs

While the technology it uses isn't very prevalent in the industry it's easy to learn the syntax so that you can focus on learning the principles.

The fact that you mentioned that it'd be cool to work on a DAW tells me that you want to go low level. What you want to study is digital signal processing or DSP. I recommend Understanding Digital Signal Processing. Also watch This talk by Timur Doumler. Or anything by him. I recommend that you pick a programming language and try to output a sin wave to the speakers, then go on from there.

Also check those out:

https://theaudioprogrammer.com/

https://jackschaedler.github.io/circles-sines-signals/

https://blog.demofox.org/#Audio

​

Good luck.

Since you brought up wellness, I'll also suggest looking into the Happiness Advantage. "Your brain at positive performs significantly better than at negative, neutral, or stressed." TED talk: http://on.ted.com/Achor (I recommend watching the entire thing, but specifically start at 9:15 if you're stretched on time). One of Shawn Achor's books:
http://amzn.com/0307591549

This one is pretty good:

https://www.amazon.co.uk/Agile-Estimating-Planning-Robert-Martin/dp/0131479415

I own a copy of the first edition of this book https://www.amazon.com/Programming-Prentice-Source-Software-Development/dp/0132354160

Now offcourse Qt has bumped to version 5 so I guess the book has followed. I remember it was very easy to follow and even I could understand it back then.

Starting Out With Python, it was a great book and helped me learn python coding.

Definitely C. It's closer to the computer and lets you see much more of what the computer is actually doing. Learn C then read this book: Computer Systems. This book will teach you the answers to the questions you want to ask but you don't even yet know about to even want to ask them.

https://cppcodetips.wordpress.com/2013/12/23/uml-class-diagram-explained-with-c-samples/
http://stackoverflow.com/questions/536648/what-is-the-best-source-for-learning-uml
http://www.amazon.com/Designing-Object-Oriented-Applications-Method/dp/0132038374